找回密码
 欢迎注册
楼主: KeyTo9_Fans

[原创] 度不超过3,直径不超过d的无向图最多有几个点?

[复制链接]
发表于 2013-5-26 18:29:23 | 显示全部楼层

7#图的对称性

7#图有20个顶点,其自同构群和对称度的计算已经超出了我的机器能力。但是,其对称阶则容易观察计算。
7#图的中心五角星是它的最短回路,也是它的唯一的5边回路。因此这5点组成一个对称类。外围五边形的顶点与五角星相邻,而边上的顶点则不邻,故它们各组成一个对称类。所以,7#图的对称阶为{5, 5, 10}.

从7#图中,我得到一个启示,猜想对于更大的 d, 最小对称阶大于1,并能够整除所有较大的对称阶。

d越大,对称阶应该越分散,所以Vmax 应该是一个有较多约数的数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-26 18:43:22 | 显示全部楼层

8# KeyTo9_Fans

能否采取一定的去重措施减少输出,并且将输出写入一个txt文件?(如果预估文件较大,为了减小文件,可以不输出固定的饱和点)。
我可以根据输出的txt文件,用M9分析对称性,理出所有不同构的图。
如果从中找到一个奇异分布的对称阶,或许可以直接推翻11#的猜想,并得到另外不同的启示。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-5-26 23:01:28 | 显示全部楼层
细数一下,其实也没有想象中的那么多解,

只是因为【距离表】很长,刷屏刷得厉害而已

【sols.txt】是边表,$1$行$1$个图,

图中的$30$条边是用$60$个整数来表示的,

第$1$、$2$个整数表示第$1$条边,

第$3$、$4$个整数表示第$2$条边,

第$5$、$6$个整数表示第$3$条边,

依次类推。

每个图的前$19$条边是固定的,后$11$条边是枚举的。

【sols.txt】一共有$128$行,也就是$128$个解。

sols.txt (19 KB, 下载次数: 7)

#####

根据楼下的指示,改拆顶点$7$和顶点$9$的边,再次枚举,又得$144$解:

sols_2.txt (21.38 KB, 下载次数: 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-27 13:16:39 | 显示全部楼层
13# KeyTo9_Fans
用M9检查的结果,128个解全部同构。
我觉得枚举可能有遗漏。你去掉的两条 3 级边都出自2级顶点9,这个一般性不明显。相反,如果从两个2级顶点上各去掉1条 3 级边,则不失一般性。这有两种情况:
1、从2级顶点7, 9上(7, 9出自2个不同的 1 级顶点)各去掉一条3级边;
2、从2级顶点8, 9上(8, 9出自同一个 1 级顶点3)各去掉一条3级边;这种情况不用考虑,已经包含在第1种情况和你已经得到的128个解中。

虽然遗漏的可能还是同构的图,万一呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-27 13:29:51 | 显示全部楼层

续10#, 彼得森图的两种非典型对称图(分享)

彼得森图是图论教科书中讲图的同构时常使用的例子,除了标准图(2#图),一般书中用来对比的图都呈三角形,大致如5#图1,反正是比较难看的.
在观察了彼得森图的自同构群(120阶啊,好大哟)后,我得到了两种新的美妙画法。我相信这个应该是咱们坛子的原创。
PetersenPraph.jpg
左图表现它的4阶自同构,右图表现了它的6阶自同构。当然还包括所有的反射自同构(2阶)。
图释:
1、左图中的3, 5,右图中的3, 4, 6都出现了两次。同一个图中重复出现2次的,为同一个点。(这是拓扑中常用的技巧)
2、所以左图中心的圆表示边(3,5).
3、右图中心的1不是6度点,还是3度点,因它的每条边相应地出现了2次
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-27 17:00:17 | 显示全部楼层

彼得森图与正十二面体

原来,彼得森图不过是坍塌的正十二面体。将正十二面体的对径点标为同一点,就同构于彼得森图。
正12面体.jpg
彼得森图具有单一的对称类(所有的顶点都彼此对称),原来如此!
15楼的两个图顿时相形见拙,不能赞美了。

评分

参与人数 1威望 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 我想过多面体,未果,你却成功了,强呀!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-28 08:08:41 | 显示全部楼层
13# KeyTo9_Fans
144解同构。鉴定完毕。

我相信6#Fans的枚举没有遗漏,所以现在可以断言:d=3时,Vmax=20,并且满足要求的图是唯一的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-28 15:06:33 | 显示全部楼层
呵呵,不错的结论,图形也很优美,很好的呢。
好像和“Degree Diameter Problem”,“Moore graph”啥的相关呢。
http://en.wikipedia.org/wiki/Moore_graph中有一个open problem:Does a Moore graph with girth 5 and degree 57 exist?曾经在一本组合的书上看到过。呵呵。

评分

参与人数 1贡献 +3 收起 理由
KeyTo9_Fans + 3 链接有参考价值

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-5-28 18:22:28 | 显示全部楼层
我今天搜“给定直径的最大正则图”,也搜到一些资料,表明这是图论中的一个Open problem. Fans好嗅觉!
3#的上限就是degree=3时的Moore bound。有一个链接中说“In general the largest degree-diameter graphs are much smaller in size than the Moore bound.”(一般情况下最大度径图的阶数远小于Moore bound).所以, Moore bound只不过是一个简单、粗放的上界。
虽然不是首问,但把degree=3的情况专门提出了,体现了Fans把握问题的分寸。degree=3的情况是最基本的,也是最有吸引力的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-5-29 21:13:47 | 显示全部楼层
当$d=4$时,找到了$1$个$n=32$的解:

0 1 0 2 0 3 1 4 1 5 2 6 2 7 3 8 3 9 4 10 4 11 5 12 5 13 6 14 6 15 7 16 7 17 8 18 8 19 9 20 9 28 10 16 10 21 11 22 11 28 12 15 12 23 13 24 13 25 14 22 14 25 15 26 16 27 17 23 17 28 18 27 18 29 19 23 19 30 20 24 20 31 21 30 21 31 22 29 24 27 25 30 26 29 26 31

但不知道最优解有几个点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 14:07 , Processed in 0.044988 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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