主題
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.tw/GraphAutomorphism.html

主題分類