圖同構

  關於滿足較弱條件的映射，請見「圖同態」和「圖同胚」。

圖同構（英語：graph isomorphism）描述的是圖論中，兩個圖之間的完全等價關係。在圖論的觀點下，兩個同構的圖被當作同一個圖來研究。

定義

一般定義

只有節點數目相同(即同階)的兩個圖才有可能同構。兩個簡單圖$G$和$H$稱為是同構的，當且僅當存在一個將$G$的節點 $1,\ldots ,n$ 映射到$H$的節點$1,\ldots ,n$的一一對應$\sigma$，使得$G$中任意兩個節點$i$和$j$相連接，當且僅當$H$中對應的兩個節點$\sigma (i)$和$\sigma (j)$相連接。同構可記作$G\simeq H$。

圖同構是圖上的等價關係，可以據此將圖劃分為等價類。一組彼此同構的圖可稱為同構圖。

如果$G$和$H$是有向圖，那麼同構的定義中還進一步要求對於$G$中任意兩個相連的節點$i$和$j$，邊$(i,j)$與它在$H$中對應的邊$(\sigma (i),\sigma (j))$方向相同。類似地可以定義兩個多重圖的同構關係。

一個具體的例子如下，為方便起見，兩圖中對應節點被染成了相同的顏色：

圖$G$	圖$H$	從圖$G$到圖$H$的同構映射$\sigma$
		$\sigma (a)=1$ $\sigma (b)=6$ $\sigma (c)=8$ $\sigma (d)=3$ $\sigma (g)=5$ $\sigma (h)=2$ $\sigma (i)=4$ $\sigma (j)=7$

要注意的一點是，在圖論中，一幅圖經常可以有多種不同的方式在紙上或屏幕上畫出來，所以兩個看起來很不同的圖也可能是同構的。尤其當圖的節點數比較大時，很難一眼從畫出的圖上判斷它們是否同構。

帶標籤的圖同構

對於帶標籤的圖，它們的同構有兩種定義。第一種定義，同構保留邊的雙射，同時包含標籤雙射。第二種定義，具有相同標籤的頂點集合被映射到同樣具有相同標籤的頂點集合，且該映射是雙射；對於邊也相同。例如，兩個頂點被標記為1和2的兩個$K_{2}$，在第一種定義下僅有其自身為同構圖，在第二種定義下，雙方互為同構圖。

在某些情況下，當圖中頂點或邊被賦予唯一且互相不同的標籤時，我們將忽略標籤存在，根據圖的基礎結構進行圖同構的判定。

研究動機

同構的概念主要關注的是，忽略一個對象中不可分割的「原子」部分的個體差異性，探索圖結構的一致性和差異性問題。這點能使我們區分圖形結構本身的屬性和與圖形結構相關聯結構的屬性（例如圖形繪製、圖標記、數據結構相關的圖等）。據此，圖同構保留了一些圖中的一些結構性的關鍵信息：角，點或邊的標籤，有根樹的根等等。

圖同構問題

在計算機科學、數學和統計學中，圖同構問題是複雜度理論研究中經常討論的熱點話題之一。圖同構問題容易和圖匹配問題混淆：

• 判定圖同構(Graph Isomorphism)問題：只需判斷兩個圖之間是否是同構的，但如果同構的話，並不要求具體找出任何做成同構的對應關係
• 圖匹配(Graph Matching)問題：判斷兩個圖是否同構，如果同構，找出至少一個使得兩者做成同構的節點間的一一對應關係

嚴格地說，兩個問題是不同的，顯然後者是比前者更進一步的問題，但也有一些論文將兩者混同並用Graph Isomorphism一詞指代Graph Matching問題。迄今尚無人嚴格證明兩者難度在P/NP意義下是相等的(要證明這一點，就必須證明第一個問題的答案可被多項式時間約化為第二個問題的答案，即：存在一個正常數$d>0$，使得對於任何一個可以判定兩個圖是否同構的算法${\cal {J}}$，若${\cal {J}}$輸出的判定為真，那麼在參考${\cal {J}}$輸出的結果的基礎上再花費至多$O(n^{d})$時間就可找出至少一個做成圖同構的一一對應)。

計算複雜度

判定圖同構(Graph Isomorphism)的計算複雜度是未知的，因此現在僅能被粗略地歸類為NP；圖匹配(Graph Matching)問題本身的複雜度同樣是未知的，但在機器學習領域非常流行的一種約化版本將其視為NP困難的QAP問題的特殊情形

$\min _{P\in \{0,1\}^{n\times n},P^{T}P=I}\left\|G-PHP^{T}\right\|_{F}$

其中$\|\cdot \|_{F}$表示矩陣的Frobenius模。該QAP約化相當於問：要求找到從$G$到$H$的一一映射，使得在此映射下兩個圖最相似。顯然圖匹配問題是該QAP問題的一種特殊情形，因為當兩個圖並不同構時，尋找兩圖間同構映射的嘗試是沒有意義的，但尋找兩圖間的一個最大化相似度的「最優映射」仍然是有意義的。尤其在當所給的數據並非圖的精確觀測而是被隨機誤差污染時，更常用該約化形式並予以近似求解。另有與兩個問題相關的更進一步的問題：

• 子圖同構(Subgraph Isomorphism)問題：給定圖$G$和圖$H$，圖$G$的節點數目小於圖$H$，問是否存在$H$的某一子圖(subgraph)，其與圖$G$同構

子圖同構已被證明是NP完全問題。

2015年，芝加哥大學教授、匈牙利裔計算機科學家László Babai宣布證明了圖同構問題可以在准多項式(Quasi-polynomial)時間內求解。哈洛德·賀歐夫各特指出了文中的一處錯誤，隨後Babai宣布修正了該錯誤並更新了論文。

對於以下的特殊情形，圖同構問題是可以多項式時間甚至快速求解的：

• 樹
• 平面圖
• 區間生成圖
• 置換生成圖
• 循環對稱圖
• 以及當任意一個下面列舉的描述圖結構性特徵的統計量被不隨節點數增長的常數上限約束時，圖同構問題可被多項式時間求解：
  • 圖的樹分解的寬度
  • 虧格
  • 最大的節點度數 (這被認為是圖同構理論迄今為止取得的最重要突破性進展之一)
  • 圖的鄰接矩陣或任何一種拉普拉斯矩陣的特徵值的最大重數

惠特尼圖同構定理

主條目：Whitney graph isomorphism theorem

The exception of Whitney's theorem: these two graphs are not isomorphic but have isomorphic line graphs.

惠特尼圖同構定理是由Hassler Whitney提出的。該定理內容是，兩個圖同構當且僅當它們的線性圖是同構的且不不包括K₃和 K_1,3。該定理可以擴展到超圖。

實用解法

與理論研究主要關注計算複雜度不同，對實用解法的研究主要關注具體應用中的實踐計算速度。P/NP問題只關注時間複雜度中$n$的指數，而不關注其係數大小。即使一個算法是多項式時間的，它也可能因$n$的係數過大導致的速度太慢及/或數值上不穩定，而在實踐中根本沒有用處；反之，一個優秀的實用解法，即使不能保證是多項式時間的，在很多應用上也可能比一些多項式時間的解法快得多。

在圖同構問題上，目前處於領先性能的實用解法是由澳大利亞計算機科學家Brendan McKay在1980年代提出的NAUTY，其對每一個圖$G$估計其節點的一個標準索引排列(Canonical Indexing，或稱Canonical Labeling)。標準索引可以非常耗時，而NAUTY算法通過探索圖的自同構性群的性質，對索引步驟進行剪枝，大大加快了標準索引的計算速度。NAUTY自從提出以來，成為了幾乎每一篇研究圖同構和圖匹配問題實用解法的論文必定要進行比較的競爭對手。

其它流行的方法包括：各色啟發式算法；對QAP約化進行SDP鬆弛；近似計算圖之間的某種不依賴於節點順序的距離，例如圖之間的編輯距離和cut distance等，這些距離的精確計算通常是NP困難的。