text: 在圖論中，圖自同構是保持自身的頂點與邊的連線關係的對稱。正式地說，圖formula_1的自同構是頂點集的置換formula_2，使得頂點對formula_3組成一條邊當且僅當formula_4也組成一條邊。也就是說，formula_2是formula_6到自身的圖同構。自同構的這個定義對有向圖和無向圖都適用。兩個自同構的複合仍是自同構，並且給定一個圖，其所有自同構的集合在複合運算下構成群，稱為這個圖的自同構群。反過來，根據Frucht定理，所有群都可以表示成連通圖的自同構群。計算複雜度.構造自同構群至少與圖同構問題一樣難，圖同構問題就是判定兩個給定的圖是否同構。因為，formula_6與formula_8同構當且僅當formula_6與formula_8的不交併有一個自同構交換兩個分支。事實上，僅僅是計算自同構的數目，就和圖同構問題以多項式時間等價。圖自同構問題就是判定一個圖是否有非平凡的自同構。它屬於計算複雜度的NP類。與圖同構問題類似，仍不知道是否有多項式時間的演算法。對於頂點度有一個常數上限的圖，相應的圖自同構問題有多項式時間的演算法。圖自同構問題可以透過多項式時間的演算法多對一歸約成圖同構問題，但反過來的歸約是否存在仍不清楚。與之不同的是，對於某些特殊型別的自同構，相應問題的難度是知道的；例如判定是否存在無不動點的自同構是NP完全的，而計算這樣的自同構的個數是#P完全的。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 圖自同構
metadata: https://zh.wikipedia.org/wiki?curid=6538128