text: 圖同構描述的是圖論中，兩個圖之間的完全等價關係。在圖論的觀點下，兩個同構的圖被當作同一個圖來研究。定義.一般定義.只有節點數目相同(即同階)的兩個圖才有可能同構。兩個簡單圖formula_1和formula_2稱為是同構的，當且僅當存在一個將formula_1的節點 formula_4 對映到formula_2的節點formula_4的一一對應formula_7，使得formula_1中任意兩個節點formula_9和formula_10相連線，當且僅當formula_2中對應的兩個節點formula_12和formula_13相連線。同構可記作formula_14。圖同構是圖上的等價關係，可以據此將圖劃分為等價類。一組彼此同構的圖可稱為同構圖。如果formula_1和formula_2是有向圖，那麼同構的定義中還進一步要求對於formula_1中任意兩個相連的節點formula_9和formula_10，邊formula_20與它在formula_2中對應的邊formula_22方向相同。類似地可以定義兩個多重圖的同構關係。一個具體的例子如下，為方便起見，兩圖中對應節點被染成了相同的顏色：要注意的一點是，在圖論中，一幅圖經常可以有多種不同的方式在紙上或螢幕上畫出來，所以兩個看起來很不同的圖也可能是同構的。尤其當圖的節點數比較大時，很難一眼從畫出的圖上判斷它們是否同構。帶標籤的圖同構.對於帶標籤的圖，它們的同構有兩種定義。第一種定義，同構保留邊的雙射，同時包含標籤雙射。第二種定義，具有相同標籤的頂點集合被對映到同樣具有相同標籤的頂點集合，且該對映是雙射；對於邊也相同。例如，兩個頂點被標記為1和2的兩個formula_23，在第一種定義下僅有其自身為同構圖，在第二種定義下，雙方互為同構圖。在某些情況下，當圖中頂點或邊被賦予唯一且互相不同的標籤時，我們將忽略標籤存在，根據圖的基礎結構進行圖同構的判定。研究動機.同構的概念主要關注的是，忽略一個物件中不可分割的“原子”部分的個體差異性，探索圖結構的一致性和差異性問題。這點能使我們區分圖形結構本身的屬性和與圖形結構相關聯結構的屬性。據此，圖同構保留了一些圖中的一些結構性的關鍵資訊：角，點或邊的標籤，有根樹的根等等。圖同構問題.在計算機科學、數學和統計學中，圖同構問題是複雜度理論研究中經常討論的熱點話題之一。圖同構問題容易和圖匹配問題混淆：嚴格地說，兩個問題是不同的，顯然後者是比前者更進一步的問題，但也有一些論文將兩者混同並用Graph Isomorphism一詞指代Graph Matching問題。迄今尚無人嚴格證明兩者難度在P/NP意義下是相等的(要證明這一點，就必須證明第一個問題的答案可被多項式時間約化為第二個問題的答案，即：存在一個正常數formula_24，使得對於任何一個可以判定兩個圖是否同構的演算法formula_25，若formula_25輸出的判定為真，那麼在參考formula_25輸出的結果的基礎上再花費至多formula_28時間就可找出至少一個做成圖同構的一一對應)。計算複雜度.判定圖同構(Graph Isomorphism)的計算複雜度是未知的，因此現在僅能被粗略地歸類為NP；圖匹配(Graph Matching)問題本身的複雜度同樣是未知的，但在機器學習領域非常流行的一種約化版本將其視為NP困難的問題的特殊情形formula_29其中formula_30表示矩陣的Frobenius模。該QAP約化相當於問：要求找到從formula_1到formula_2的一一對映，使得在此對映下兩個圖最相似。顯然圖匹配問題是該QAP問題的一種特殊情形，因為當兩個圖並不同構時，尋找兩圖間同構對映的嘗試是沒有意義的，但尋找兩圖間的一個最大化相似度的“最優對映”仍然是有意義的。尤其在當所給的資料並非圖的精確觀測而是被隨機誤差汙染時，更常用該約化形式並予以近似求解。另有與兩個問題相關的更進一步的問題：子圖同構已被證明是NP完全問題。2015年，芝加哥大學教授、匈牙利裔計算機科學家宣佈證明了圖同構問題可以在準多項式(Quasi-polynomial)時間內求解。哈洛德·賀歐夫各特指出了文中的一處錯誤，隨後Babai宣佈修正了該錯誤並更新了論文。對於以下的特殊情形，圖同構問題是可以多項式時間甚至快速求解的：惠特尼圖同構定理.惠特尼圖同構定理是由Hassler Whitney提出的。該定理內容是，兩個圖同構當且僅當它們的線性圖是同構的且不不包括"K"3和 "K"1,3。該定理可以擴充套件到超圖。實用解法.與理論研究主要關注計算複雜度不同，對實用解法的研究主要關注具體應用中的實踐計算速度。P/NP問題只關注時間複雜度中formula_39的指數，而不關注其係數大小。即使一個演算法是多項式時間的，它也可能因formula_39的係數過大導致的速度太慢及/或數值上不穩定，而在實踐中根本沒有用處；反之，一個優秀的實用解法，即使不能保證是多項式時間的，在很多應用上也可能比一些多項式時間的解法快得多。在圖同構問題上，目前處於領先效能的實用解法是由澳大利亞計算機科學家在1980年代提出的NAUTY，其對每一個圖formula_1估計其節點的一個標準索引排列(Canonical Indexing，或稱Canonical Labeling)。標準索引可以非常耗時，而NAUTY演算法透過探索圖的自同構性群的性質，對索引步驟進行剪枝，大大加快了標準索引的計算速度。NAUTY自從提出以來，成為了幾乎每一篇研究圖同構和圖匹配問題實用解法的論文必定要進行比較的競爭對手。其它流行的方法包括：各色啟發式演算法；對QAP約化進行鬆弛；近似計算圖之間的某種不依賴於節點順序的距離，例如圖之間的編輯距離和cut distance等，這些距離的精確計算通常是NP困難的。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 圖同構
metadata: https://zh.wikipedia.org/wiki?curid=6343842