圖自同構

在圖論中，圖自同構（graph automorphism）是保持自身的頂點與邊的連接關係的對稱。

正式地說，圖 $G=(V,E)$ 的自同構是頂點集的置換 $\sigma$ ，使得頂點對 $(u,v)$ 組成一條邊當且僅當 $(\sigma (u),\sigma (v))$ 也組成一條邊。也就是說， $\sigma$ 是 $G$ 到自身的圖同構。自同構的這個定義對有向圖和無向圖都適用。兩個自同構的複合仍是自同構，並且給定一個圖，其所有自同構的集合在複合運算下構成群，稱為這個圖的自同構群。反過來，根據Frucht定理，所有群都可以表示成連通圖的自同構群^[1]^[2]。

計算複雜度

構造自同構群至少與圖同構問題一樣難（在計算複雜度的意義下），圖同構問題就是判定兩個給定的圖是否同構。因為， $G$ 與 $H$ 同構當且僅當 $G$ 與 $H$ 的不交並有一個自同構交換兩個分支^[3]。事實上，僅僅是計算自同構的數目，就和圖同構問題以多項式時間等價^[4]。

佩特森圖的這種畫法顯示出其對稱的一個子群，同構於二面體群

D_{5}

，但這個圖還有其他的對稱性沒有體現在這種畫法中。例如，因為這個圖是對稱的，所有邊都是等價的。

圖自同構問題就是判定一個圖是否有非平凡的自同構。它屬於計算複雜度的NP類。與圖同構問題類似，仍不知道是否有多項式時間的算法^[5]。對於頂點度有一個常數上限的圖，相應的圖自同構問題有多項式時間的算法^[3]。圖自同構問題可以通過多項式時間的算法多對一歸約成圖同構問題，但反過來的歸約是否存在仍不清楚^[4]^[6]^[7]。與之不同的是，對於某些特殊類型的自同構，相應問題的難度是知道的；例如判定是否存在無不動點的自同構是NP完全的，而計算這樣的自同構的個數是#P完全的^[5]^[7]。

根據自同構定義的圖族

不對稱圖是沒有非平凡自同構的無向圖。
對稱圖是每一對鄰接的頂點都可以通過一個自同構變成任何其他一對鄰接頂點的圖。
反對稱圖是有一個頂點的置換 $\sigma$ 把邊變成反方向的邊的有向圖，而且要求 $\sigma$ 是對合。

另見

代數圖論

參考資料

^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
^ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987.
^ ^3.0 ^3.1 Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5.
^ ^4.0 ^4.1 Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8: 131–132. doi:10.1016/0020-0190(79)90004-8.
^ ^5.0 ^5.1 Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.
^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287
^ ^7.0 ^7.1 Jacobo Torán, "On the hardness of graph isomorphism", SIAM Journal on Computing, vol. 33 (2004), no. 5, pp. 1093-1108, doi:10.1137/S009753970241096X

外部連結

埃里克·韋斯坦因 "Graph Automorphism"（頁面存檔備份，存於網際網路檔案館）MathWorld

[1] Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.

[2] Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987.

[Luks,_Eugene_M.-3] 3.0 ^3.1 Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5.

[Mathon,_R._(1979)-4] 4.0 ^4.1 Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8: 131–132. doi:10.1016/0020-0190(79)90004-8.

[Lubiw,_Anna_(1981)-5] 5.0 ^5.1 Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.

[6] Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287

[Jacobo-7] 7.0 ^7.1 Jacobo Torán, "On the hardness of graph isomorphism", SIAM Journal on Computing, vol. 33 (2004), no. 5, pp. 1093-1108, doi:10.1137/S009753970241096X

[1]

[2]

[3]

[4]

[5]

[6]

[7]