度不超过3，直径不超过d的无向图最多有几个点？

KeyTo9_Fans

一个无向图由若干个顶点和连接2个顶点的若干条无向边组成。 一个顶点的度就是与该顶点有边相连的点数。

图的直径就是相距最远的2个顶点的距离。 2个顶点的距离就是从1个顶点出发，按照图中的边走到另1个顶点所经过的最少边数。 如果从1个顶点出发，按照图中的边无法走到另1个顶点，我们就认为这2个顶点的距离是$+\infty$。 问：每个顶点的度都不超过$3$，直径不超过$d$的无向图最多可以有多少个顶点？ 例如： 当$d=0$时，最多有$1$个点，这个点的度是$0$。 当$d=1$时，最多有$4$个点，这$4$个点两两相连，每个点的度都恰好是$3$。 那么，对于更大的$d$，答案是多少呢？

hujunhua

d=2时，Vmax=10，为PetersenGraph(5,2)

hujunhua

容易给出一个简单的上限。 以d=2为例。先给定一个3度点（始点），它发出3条边，指向3个顶点（1 级顶点），其余的顶点必须与 1 级顶点相连。而每个 1 级顶点最多再发出2边条，指向2个顶点（二级顶点），故最多6个二级顶点。所以d=2时，最多10个顶点。 对于更多大的 d, 逐级类推，最多$3*2^d-2$个点。对于d=3，这个上限为22。22个顶点的3度图已经很多了，想用编程搜索的办法来解这个问题，估计走不了多远。

gxqcn

2# hujunhua 我也曾想到五角星，但没想到如此美妙的方案。

hujunhua

我最初画出来的图是下面这样的： 过程如下：先确定一个3度点为始点（10），然后生成 1 级点（1，2，3）和 2 级点（4~9）。始点和 1 级点都是3度点了，度数已饱和，所以只需要考虑6个二级点构成的二度图（6个 2 级点已各有1 边，不在所考虑的子图内）。假定图的连通效率最高，则最短回路的长度必定为5. 所以6个二级点构成的二度图应该是一个长度为6的回路。在这两条的启示下，很容易作出余下的边。 将这种方法推广到d=3的情况，首先得到如下的图， 同样，只有末级点是未饱和点，只需要考虑12个末级点（10~21）构成的二度图。这时再用编程搜索的方法应该可行了。

KeyTo9_Fans

很遗憾， $22$个点， 如上图所示固定$21$条边， 枚举另外$12$条边， 躺等一晚上， 枚举完了， 结果是无解。 我现在迷茫了， 答案不是$(3*2^d-2)$， 会是多少呢？

hujunhua

如果包含2度点，易知最多11点，故必须是3-正则图，则由3V=2E知顶点必为偶数。所以最多只可能是20点了。我手工搞出一个20点的方案（老婆召唤吃午饭，没来得及全面检查，貌似没问题）。 至于有没有其它更好的方案，我就不知道了。Fans可以从5#的图中去掉2个末级点搜索一下。

KeyTo9_Fans

去掉$2$个末级点之后枚举剩余的边， 结果可行方案一个接一个地如泉涌般蹦出来， 我只好按下pause键，才能抓住一个放上来：

1. 01112222223333333333
2. 10221133332222333333
3. 12023311333333222233
4. 12203333113332332322
5. 21330233331133222323
6. 21332033323311233232
7. 23133302332232113332
8. 23133320323223331123
9. 23313333022323323211
10. 23313232203231231333
11. 32331323230232133213
12. 32331322322033311332
13. 32333132233302323121
14. 32323123312320132333
15. 33232213321331023323
16. 33232313233123202331
17. 33222331313132320233
18. 33233231232313332012
19. 33322332131323233102
20. 33323223133213313220

复制代码

我的程序输出的是距离表，表中的第$i$行第$j$列表示第$i$个顶点与第$j$个顶点的距离。 我们可以看到，整张表有$20$行、$20$列，距离的最大值是$3$，是一个$d=3$、$n=20$的可行解。 因此我们可以相信hujunhua版主所说的【d=3，Vmax=20】属实无误。

hujunhua

【d=3，Vmax=20】 是否确实，关键在于你在6#的枚举有没有漏洞。 8#用Pause键抓住的那个解，我连了一下，还是7#的那个图。难道这个是唯一解？ 我有点不相信，我可是手工在纸上试出来的呀，难道是人品大暴发，两刷子就碰到了这个唯一解了？

hujunhua

极限往往与对称性相伴而行，因此考察一下图的对称性或许可得到一些有用的启示。 先罗列几个与图的对称性有关的基本概念和定义。 定义1【图的自同构】图G:={V,E}, f是顶点集 V 的一个变换，若 f(E)=E, 则称 f 为图 G 的一个自同构。 性质1【图的自同构群】图G的所有自同构组成的集合构成群，称为图G的自同构群。 定义2【图的对称度】图的自同构群的阶。 定义3【图的对称点】图G={V,E},v1,v2∈V，若存在G的一个自同构f，使得f(v1)=v2, 则称v1,v2是对称的。 定义4【对称阶】顶点集 V 按对称关系所划分的对称类的阶。 例1：G=简单四边形1234. 写出G的自同构群、对称度、对称阶 自同构群H={(1234),(13),(24),(2341),(12)(34),(14)(23),(13)(24),(4123)} 所以简单四边形的对称度为8。显然，简单四边形的顶点集只有一个对称类，故对称阶为4. 从简单四边形的自同构群来看，将图画成正方形就能完全表现其对称性。 例2：PeterGraph(5,2)（即2#图） 这个图有10个顶点，其自同构群凭手工计算已经不容易了，用M9计算的结果表明，其对称度为120. 相对而言，对称阶更容易观察和计算。2#图的顶点集属于全属于一个对称类，故对称阶为10. 5#的第1个图表现了PeterGraph(5,2)的非5阶对称性，可见2#图没有完全表现PeterGraph(5,2)的对称性。 M9计算出来的自同构群揭示了彼得森图的另外2种令人惊异的几何表现（分享容后）。