用戶:SandoClemento2014/圖同構

圖同構(Graph Isomorphism)描述的是圖論中，兩個圖之間的完全等價關係。在圖論的觀點下，兩個同構的圖被當作同一個圖來研究。

定義

只有節點數目相同(即同階)的兩個圖才有可能同構。兩個簡單圖$G$和$H$稱為是同構的，若且唯若存在一個將$G$的節點 $1,\ldots ,n$ 映射到$H$的節點$1,\ldots ,n$的一一對應$\sigma$，使得$G$中任意兩個節點$i$和$j$相連接，若且唯若$H$中對應的兩個節點$\sigma (i)$和$\sigma (j)$相連接。如果$G$和$H$是有向圖，那麼同構的定義中還進一步要求對於$G$中任意兩個相連的節點$i$和$j$，邊$(i,j)$與它在$H$中對應的邊$(\sigma (i),\sigma (j))$方向相同。類似地可以定義兩個多重圖的同構關係。

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

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

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

圖同構問題

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

• 判定圖同構(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困難。另有與兩個問題相關的更進一步的問題：

• 子圖同構/匹配(Subgraph Isomorphism/Matching)問題：給定圖$G$和圖$H$，圖$G$的節點數目小於圖$H$，問是否存在$H$的某一子圖(subgraph)，其與圖$G$同構，或更進一步地要求找出至少一個此種同構

無論是子圖同構還是子圖匹配都是NP完全問題。

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

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

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

實用解法

目前最具代表性的實用解法是由澳大利亞計算機科學家Brendan McKay提出的NAUTY，其對每一個圖$G$估計其節點的一個標準索引排列(Canonical Indexing，或稱Canonical Labeling)，但標準索引可能非常耗時，而NAUTY算法通過對圖的自同構性質的利用大大加快了標準索引的計算速度。