zhouguang 发表于 2015-5-12 10:05:32

一个关于图的对称性的问题

如果一个图的各个节点引出的线都一样多（即：一个无向简单图的各节点的度均相同的正则图），那么是否可以断定必然存在一个节点的置换，使得置换前后的图完全一样？（即：能否断定这个简单图的自同构群必定不是I？）

mathe 发表于 2015-5-12 13:42:16

16个点24边 AB AC AD BE BF CD CG DH EF EI FL GM GO HI HK IL JM JN JK KL MP NO NP OP

mathe 发表于 2015-5-12 13:54:44

首先图中仅三个三角形ACD,BEF,ONP将9个点与其余7点区分。9个点间关系区分了OPN的特殊性，然后余下7点和三角形连接关系中K不直接关连，G直接关联两三角形完全确定K,G的特殊性已经三个三角形的不同。余下唯一性就容易确定了

hujunhua 发表于 2015-5-12 16:25:31

16个结点！能比这更少么？

zhouguang 发表于 2015-5-12 22:41:40

能引起两位大佬的注意，荣幸呀，呵呵。
http://en.m.wikipedia.org/wiki/Frucht_graph
根据上面链接的说法，可以12个点。
页: [1]
查看完整版本: 一个关于图的对称性的问题