找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

  [复制链接]
发表于 2008-8-5 18:05:24 | 显示全部楼层
对第二个问题,就是n个字母,取出x组,每组4个字母,每两组之间最多1个相同的字母。
我写了个简单的程序计算出了$n<=15$时x的最大值$x(n)$,而且得出
$17<=x(16)<=20$
$20<=x(17)<=21$
$21<=x(18)<=22$
结果惊奇的发现这个序列同
A004037匹配上了。
也就是x(5)是这个序列中第一个数或者说$x(n+4)=A(n,6,4)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 09:32:17 | 显示全部楼层
这个不惊奇,第二个问题有很多种描述方法,比如:将Kn分解为K4的最大树。
如果再加一点要求,让所有点出现的次数相等,则是一个S(2,4,n)的steiner系统。
上述steiner系统在12|n(n-1)时存在,所以 x(16)=C(16,2)/C(4,2)=20,x(21)=35,x(25)=50 ......
对于n=20,我觉得zgg差不多了,没找到有效的构造方法,我想只能强搜了。

[ 本帖最后由 shshsh_0510 于 2008-8-6 10:01 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 09:39:47 | 显示全部楼层
呵呵,仔细看了一下, 就是mathe 的连接,  Optimal packings of K_4's into a K_n,
那么x(20)应该是42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 09:43:54 | 显示全部楼层
好像数不太队,在想想
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 09:53:01 | 显示全部楼层
呵呵,没看清楚,那个“  Optimal packings of K_4's into a K_n, ” 是一个ref,不是对这个数列的描述。
找到那个ref就ok了。我没找到,谁找一下啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 10:41:16 | 显示全部楼层
对于两个问题等价问题,很容易证明,比如对于n=16时不等价。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-6 11:02:09 | 显示全部楼层
原帖由 shshsh_0510 于 2008-8-6 09:39 发表
呵呵,仔细看了一下, 就是mathe 的连接,  Optimal packings of K_4's into a K_n,
那么x(20)应该是42

你不说optimal packing $K_4$'s into $K_n$,我倒没有注意。这个说法倒应该没有错了。
只是这个数列不是从第1项开始的,链接中说是第6项开始,但是我觉得应该是第5项开始。
而x(20)应该是30,而不是42。
里面$A(n,d,w)$的提法也应该是正确的,只是我觉得应该是$A(n,7,4)$而不是$A(n,6,4)$,而且同样是从第5项而不是第6项开始的。
也就是描述成最大的长度为n重量为4的0-1向量集合,其中任何两向量海明距离不小于7。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-8 17:48:31 | 显示全部楼层
关于问题1,网上资料只能查到$n<=11$的值。
我写的一个程序现在计算出了关于问题2中$12<=n<=14$所有不等价的边的数目不小于
$[{[(n-1)/3]n}/4]-3$的组合,总数不多,大家可以看看能否通过它们构造第一个问题的解

result.tar.gz

1.35 KB, 下载次数: 9, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-8 17:56:34 | 显示全部楼层
忘了说明数据格式,每一行代表一个组合。其中相邻4个字母代表一条直线
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-9 11:30:02 | 显示全部楼层
对于问题二的x(20),搜索到一组为27的解:
{{5,8,13,20},{3,12,13,17},{1,6,7,13},{1,8,14,15},{4,9,13,16},{9,11,18,19},{7,12,16,19},{2,3,6,20},{2,8,11,12},{3,5,14,19},{5,10,16,18},{1,5,11,17},{7,15,18,20},{1,9,12,20},{2,5,7,9},{4,6,10,11},{4,5,12,15},{6,12,14,18},{2,10,13,19},{1,2,4,18},{2,15,16,17},{4,17,19,20},{7,10,14,17},{11,14,16,20},{3,4,7,8},{6,8,9,17},{3,9,10,15}}
可以看到,其中有8个数出现了6次,有12个出现了5次。我们知道一个数只能最多出现6次(因为只有19个数可以和它配组,[19/3]=6)。如果20个数都恰好出现6次,那么总共有120个数,120/4=30,所以只有每个数都出现6次,才能构成x(20)=30的解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 08:36 , Processed in 0.060875 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表