主题
Search

图自同构

下载 Mathematica 笔记本下载 Wolfram 笔记本

图的自同构是指其自身的图同构，即从给定图 G 的顶点到 G 顶点的映射，使得结果图与 G 同构。自同构的集合定义了一个置换群，称为该图的自同构群。对于每个群 Gamma，都存在一个图，其自同构群与 Gamma 同构（Frucht 1939；Skiena 1990，第 185 页）。图的自同构群表征了其对称性，因此在确定其某些性质时非常有用。

图 G 的图自同构群可以使用 Wolfram 语言 计算，方法如下GraphAutomorphismGroup[g]，其元素可以使用以下方法提取GroupElements。存在许多用于计算图自同构的软件实现，包括 Brendan McKay 的 nauty 和 SAUCY2，后者在经验测试中比其他实现快几个数量级（Darga等人2008 年）。

可以使用以下方法获取许多命名图的预计算自同构GraphData[graph,"Automorphisms"]，以及使用以下方法获取自同构的数量GraphData[graph,"AutomorphismCount"].

GraphAutomorphismGridGraph

例如，网格图 G_(2,3) 有四个自同构：（1, 2, 3, 4, 5, 6）、（2, 1, 4, 3, 6, 5）、（5, 6, 3, 4, 1, 2）和（6, 5, 4, 3, 2, 1）。这些分别对应于图本身、左右翻转的图、上下翻转的图以及左右和上下翻转的图，如上图所示。更一般地，正如其对称性所表明的那样，

|Aut(G_(m,n))|={1 for m=n=1; 2 for m=1 or n=1; 4 for m!=n and m,n>1; 8 for m=n>1.
(1)
GraphAutomorphismStar

类似地，星图 S_4 有六个自同构：（1, 2, 3, 4）、（1, 3, 2, 4）、（2, 1, 3, 4）、（2, 3, 1, 4）、（3, 1, 2, 4）、（3, 2, 1, 4），如上图所示。更一般地，正如其对称性所表明的那样，对于 n>=3，|Aut(S_n)|=(n-1)!。

下表总结了各种图类的 |Aut(G_n)|。

图OEIS序列
反棱柱图，n>=3A12435448, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
完全图 K_nA0000001, 2, 6, 24, 120, 720, ...
环图 C_n，n>=3A0000006, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, ...
超立方体图 Q_nA0001652, 8, 48, 384, 3840, 46080, 645120, 10321920, ...
莫比乌斯梯子图，n>=3A00000072, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
棱柱图，n>=3A12435112, 48, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
轮图 W_n，n>=4A00000024, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ...

图补图的自同构群与原始图的自同构群相同。仅具有单个自同构的图称为恒等图（Holton 和 Sheehan 1993，第 24 页），有时也称为非对称图。 n=1、2、... 个节点的自同构图的排序长度三角形由下式给出

1 2 2 2 2 6 6 2 2 2 4 4 6 6 8 8 24 24 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 6 6 8 8 8 8 10......12 12 12 12 12 12 24 24 120 120
(2)

（OEIS A075094）。

简单图的自同构群的不同阶数的数量（节点数为 n=1、2、...）为 1、1、2、5、8、14、19、30、45、...（OEIS A095348）。

下表给出了具有给定自同构群阶数的 n 节点简单图的数量计数。

|Aut(G)|OEIS具有 1、2、... 个节点的图的计数
1A0034000, 0, 0, 0, 0, 8, 152, 3696, 135004, ...
2A0750950, 2, 2, 3, 11, 46, 354, 4431, 89004, ...
30, 0, 0, 0, 0, 0, 0, 0, 4, ...
4A0750960, 0, 0, 2, 6, 36, 248, 2264, 31754, ...
6A0750970, 0, 2, 2, 2, 8, 38, 252, 3262, ...
8A0750980, 0, 0, 2, 4, 14, 74, 623, 7003, ...
100, 0, 0, 0, 1, 2, 2, 4, 16, ...
12A0958530, 0, 0, 0, 6, 18, 70, 446, 3924, ...
140, 0, 0, 0, 0, 0, 2, 4, 4, ...
16A0958540, 0, 0, 0, 0, 6, 20, 164, 1280, ...
180, 0, 0, 0, 0, 0, 0, 0, 4, ...
200, 0, 0, 0, 0, 0, 4, 12, 42, ...
24A0958550, 0, 0, 2, 2, 2, 24, 170, 1570, ...
320, 0, 0, 0, 0, 0, 0, 24, 176, ...
36A0958560, 0, 0, 0, 0, 2, 6, 22, 164, ...
48A0958570, 0, 0, 0, 0, 8, 28, 96, 660, ...
72A0958580, 0, 0, 0, 0, 2, 4, 28, 179, ...
1200, 0, 0, 0, 2, 2, 2, 6, 26, ...
1440, 0, 0, 0, 0, 0, 6, 24, 78, ...
2400, 0, 0, 0, 0, 0, 6, 16, 70, ...
7200, 0, 0, 0, 0, 2, 2, 8, 22, ...

具有阶数为 n 的自同构群的最小图的顶点数为 0、2、9、4、15、3、14、4、15、5、...（OEIS A080803）。下表总结了达到这些界限的图，其中 E_n 和 C_n 分别表示 n 个节点上的空图和环图。令 G_1 union G_2 表示图的并，G^' 表示 G 的图补图。此外，令 A_n 为具有顶点 {a_i,b_i,c_i:0<=i<n} 和边 {(a_i,a_(i+1)),(a_i,b_i),(a_i,c_i),(b_i,c_i),(c_i,a_(i+1)):0<=i<n} 的图，其中所有索引都应按模 n 读取（即 A_n 由一个 n 边形 (a_0,...,a_(n-1)) 组成，每个边上绘制一个矩形，并且每个矩形中有一条对角线）。令 (A_n)/m 为通过将 A_n 中的 b_i 与每个 b_j 标识而从 A_n 获得的图，其中 i 与 j 模 (n/m) 同余，对于 c_i 也是如此。此外，令 B_n 为具有顶点 {a_i,b_i:0<=i<n} 和边 {(a_i,a_(i+1)),(a_i,b_(i-1)),(a_i,b_i),(a_i,b_(i+1)),(a_i,b_(i+3)):0<=i<n} 的图，其中所有索引都按模 n 取模（Voss 2003）。

|Aut(G)|图 G|G|
1E_00
2E_22
3A_39
4K_2 union E_24
5A_515
6C_33
7B_714
8C_44
9(A_9)/315
10C_55
11B_(11)22
12C_3 union E_25
13B_(13)26
14C_77
15(A_(15))/521
16C_4 union E_26
17B_(17)34
18C_99
19B_(19)38
20C_5 union E_27
21B_7 union A_323
22C_(11)11
23B_(23)46
24E_44
25A_5 union A_5^'30
26C_(13)13
27(A_9)/3 union A_324
28C_7 union E_29
29B_(29)58
30A_3 union C_514
31B_(31)62

下表给出了许多常见图的图自同构群。

GAut(G)
完全图 K_n对称群 S_n
空图 E_n对称群 S_n
环图 C_n，n>=3二面体群 D_n
K_2 union E_2有限群 C2×C2
C_n union E_2, n>=3有限群 D_(2n)×C_2
A_n 如上定义循环群 C_n
B_n 如上定义循环群 C_(2n)

自同构群为循环群的简单图可以称为循环群图。最小的非平凡循环群图有九个节点。

另请参阅

自同构群、循环群图、边自同构、边自同构群、边传递图、Frucht 图、图同构、同构图、顶点传递图

在 中探索

参考文献

Darga, P. T.; Sakallah, K. A.; 和 Markov, I. L. "Faster Symmetry Discovery using Sparsity of Symmetries." Proceedings of the 45th Design Automation Conference, Anaheim, California, June 2008. 2008. http://vlsicad.eecs.umich.edu/BK/SAUCY/saucy-dac08.pdf.Douglas, B. L. 和 Wang, J. B. "A Classical Approach to the Graph Isomorphism Problem Using Quantum Walks." J. Phys. A: Math. Theor. 41, 075303-1-15, 2008.Duijvestijn, A. J. W. "Algorithmic Calculation of the Order of the Automorphism Group of a Graph." Memorandum No. 221. Enschede, Netherlands: Twente Univ. Technology, 1978.Frucht, R. "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compos. Math. 6, 239-250, 1939.Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Holton, D. A. 和 Sheehan, J. 彼得森图。 Cambridge, England: Cambridge University Press, 1993.Lauri, J. 和 Scapellato, R. 图自同构与重构主题。 Cambridge, England: Cambridge University Press, 2003.Lipton, R. J.; North, S. C.; 和 Sandberg, J. S. "A Method for Drawing Graphs." In Proc. First Annual Symposium on Computation Geometry (Ed. J. O'Rourke). New York: ACM Press, pp. 153-160, 1985.McKay, B. "The Nauty Page." http://cs.anu.edu.au/~bdm/nauty/.Skiena, S. "Automorphism Groups." §5.2.2 in 实现离散数学：组合学和图论与 Mathematica。 Reading, MA: Addison-Wesley, pp. 184-187, 1990.Sloane, N. J. A. 序列 A000165/M1878, A003400/M4575, A075095, A075096, A075097, A075098, A080803, A095348, A124351, 和 A124354 在 "整数序列在线百科全书" 中。University of Michigan Electrical Engineering and Computer Science department. "Saucy: Fast Symmetry Discovery." http://vlsicad.eecs.umich.edu/BK/SAUCY/.Voss, J. "Re: RE: Graphs with automorphism groups of given order." seqfan@ext.jussieu.fr 邮件列表. March 27, 2003.

在 上引用

图自同构

请引用为

Weisstein, Eric W. "图自同构。" 来自 Web 资源。 https://mathworld.net.cn/GraphAutomorphism.html

主题分类