有沒有什麼演算法可以確定兩圖是否同構？

01-04

[子圖同構](Subgraph isomorphism problem)是NP-complete問題

[圖同構](Graph isomorphism)是NP問題，但是既沒有人找到多項式演算法(證明是P問題)，也沒有人能證明是NP-complete問題。

我們可以用Hash的方法以一定的概率確定兩圖是否同構。1.楊弋《Hash在信息學競賽中的一類應用》

@管清文說的很好，我補充幾個圖同構常用演算法：

Ullmann演算法、VF演算法和他的升級版VF2演算法。VF2是常用演算法裡面效率比較高的，但是還有一篇最新的vf2x，號稱在VF2的基礎上提升了一個數量級。

這裡有一篇對於5種圖同構演算法的綜述，Experiments中詳細比較了5種常用演算法性能的優劣，可以給你一個宏觀的了解：

A Performance Comparison of Five Algorithms for Graph Isomorphism

update一篇15年的圖同構的偽多項式演算法

http://arxiv.org/abs/1512.03547

現在比較好的解決圖同構的方法有QuickSI SPATH 基於索引的gindex fpindex和最近的vldb的boostiso和turboiso

NP-hard 問題，比較好的近似方法，GNCCP，複雜度在O(n^3)，n為節點數，我boss2014年在pami發表的論文，覺得他這篇文章的證明過程很美~~

GNCCP - Graduated NonConvexity and Concavity Procedure

Zhi-Yong Liu* and Hong Qiao. IEEE Transactions on Pattern Analysis and Machine Intelligence: 2014,36(6) ,1258-1267

有沒有什麼必要條件或充分條件，不要求每次都判斷正確，有一定的誤判也行