Can you summarize the following document?
        
  只有節點數目相同(即同階)的兩個圖才有可能同構。兩個簡單圖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_1和formula_2是有向圖,那麼同構的定義中還進一步要求對於formula_1中任意兩個相連的節點formula_9和formula_10,邊formula_19與它在formula_2中對應的邊formula_21方向相同。類似地可以定義兩個多重圖的同構關係。  一個具體的例子如下,為方便起見,兩圖中對應節點被染成了相同的顏色:  要注意的一點是,在圖論中,一幅圖經常可以有多種不同的方式在紙上或螢幕上畫出來,所以兩個看起來很不同的圖也可能是同構的。尤其當圖的節點數比較大時,很難一眼從畫出的圖上判斷它們是否同構。

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

  判定圖同構(Graph Isomorphism)的計算複雜度是未知的,因此現在僅能被粗略地歸類為NP;圖匹配(Graph Matching)問題本身的複雜度同樣是未知的,但在機器學習領域非常流行的一種約化版本將其視為NP困難的QAP問題的特殊情形 其中formula_28表示矩陣的Frobenius模。該QAP約化相當於問:要求找到從formula_1到formula_2的一一對映,使得在此對映下兩個圖最相似。顯然圖匹配問題是該QAP問題的一種特殊情形,因為當兩個圖並不同構時,尋找兩圖間同構對映的嘗試是沒有意義的,但尋找兩圖間的一個最大化相似度的“最優對映”仍然是有意義的。尤其在當所給的資料並非圖的精確觀測而是被隨機誤差汙染時,更常用該約化形式並予以近似求解。另有與兩個問題相關的更進一步的問題: 子圖同構已被證明是NP完全問題。  2015年,芝加哥大學教授、匈牙利裔電腦科學家László Babai宣佈證明了圖同構問題可以在準多項式(Quasi-polynomial)時間內求解。哈洛德·賀歐夫各特指出了文中的一處錯誤,隨後Babai宣佈修正了該錯誤並更新了論文。  對於以下的特殊情形,圖同構問題是可以多項式時間甚至快速求解的:

  與理論研究主要關注計算複雜度不同,對實用解法的研究主要關注具體應用中的實踐計算速度。P/NP問題只關注時間複雜度中formula_37的指數,而不關注其係數大小。即使一個演算法是多項式時間的,它也可能因formula_37的係數過大導致的速度太慢及/或數值上不穩定,而在實踐中根本沒有用處;反之,一個優秀的實用解法,即使不能保證是多項式時間的,在很多應用上也可能比一些多項式時間的解法快得多。  在圖同構問題上,目前處於領先效能的實用解法是由澳大利亞電腦科學家Brendan McKay在1980年代提出的NAUTY,其對每一個圖formula_1估計其節點的一個標準索引排列(Canonical Indexing,或稱Canonical Labeling)。標準索引可以非常耗時,而NAUTY演算法通過探索圖的自同構性群的性質,對索引步驟進行剪枝,大大加快了標準索引的計算速度。NAUTY自從提出以來,成為了幾乎每一篇研究圖同構和圖匹配問題實用解法的論文必定要進行比較的競爭對手。  其它流行的方法包括:各色啟發式演算法;對QAP約化進行SDP鬆弛;近似計算圖之間的某種不依賴於節點順序的距離,例如圖之間的編輯距離和cut distance等,這些距離的精確計算通常是NP困難的。
圖同構(Graph Isomorphism)描述的是圖論中,兩個圖之間的完全等價關係。在圖論的觀點下,兩個同構的圖被當作同一個圖來研究。