跳至內容

用戶:SandoClemento2014/圖同構

維基百科,自由的百科全書

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

定義

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

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

從圖到圖的同構映射

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

圖同構問題

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

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

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

計算複雜度

判定圖同構(Graph Isomorphism)的計算複雜度是未知的,因此現在僅能被粗略地歸類為NP圖匹配(Graph Matching)問題的複雜度是NP困難。另有與兩個問題相關的更進一步的問題:

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

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

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

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


實用解法

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

參考文獻

  1. ^ Babai, László, Graph Isomorphism in Quasipolynomial Time, 2015, Bibcode:2015arXiv151203547B, arXiv:1512.03547可免費查閱 
  2. ^ Babai, László, Graph isomorphism update, January 9, 2017 
  3. ^ NAUTY -- Graph Isomorphism.