摘要: 轉載請注明來自stanlysheng——talk is cheap, show me your code。http://www.cnblogs.com/stanly/?。謝謝。此文我也在CSDN發過。

最近在學習子圖同構算法。什么是子圖同構，看這里-->圖論。在圖論的維基百科中有子圖同構的描述。

子圖同構一直是圖論中比較重要的一個問題，經過各位大牛長時間的學習和研究，發現求解子圖同構是一個NP完全問題。什么是NP完全問題，可以戳這里--->NP完全。

在經過不斷地搜索和閱讀論文，發現了不少論文都在討論子圖同構算法。出現得比較多并且很多人都知道并認可的，有這么幾種算法：Ullmann算法、Nauty算法、SD算法、VF算法以及在VF算法上進行改進的VF2算法。其中Ullmann算法應該是最早提出的可以找到子圖同構的算法。因此現在學習圖論如果設計到同構，雖然不會用ullmann算法，但是一般都會以其作為對子圖同構的基礎進行了解和學習。中間三種算法尚未研究，以后可能會看，因為時間和研究原因我的重點在第一個ullmann和最后的公認最好的VF2算法。

在最壞情況下，ullmann算法的時間復雜度與圖中節點數目的指數成正比。ullmann算法以深度優先的方式進行搜索，搜索過程表示為一個布爾矩陣。當節點不匹配時則回溯到最近匹配的節點，尋找其他的搜索方向。同時，算法還會檢查匹配點對的鄰接點的匹配情況，盡可能早的識別出不可匹配的節點。提高算法的效率。

先介紹深度優先的簡單窮舉方法，這個階段不包含上面說的檢查匹配點對的鄰接點的匹配情況（即refine procedure），將在后面我寫好代碼之后再發。

此搜索方法其實是深度優先遍歷兩圖的關聯矩陣，來找到滿足其子圖同構的關聯矩陣。

對于給定的兩個圖，是從節點數目大的那個圖中尋找部分節點和邊，和節點數目小的圖是同構的。

圖G1=<V1，E1>,G2=<V1，E1>，G1 和G2 的節點數分別為p1和p2。他們的鄰接矩陣表示分別為A=[aij]和B=[bij]。

該算法要尋找的同構關系表現為尋找兩圖的一個關聯矩陣M，這是一個p1*p2的矩陣，其元素mij表示G1的第 i 個節點和G2的第 j 個節點是否對應。因此這個矩陣的限制為：每行只有一個1，而每列最多只有一個1 。因此mij==1表示G1的第 i 個節點和G2的第 j 個節點對應。否則不對應。

條件（1）判定：當找到這樣一個M`的時候我們進行如下操作得到另一個p1*p1的矩陣C，定義C為：C=M`（M`B）T，后面的T表示（M`B）做轉置。即M`乘以[（M`B）的轉置]得到C，如果對于每一個i , j 都屬于（1，p1）都滿足當aij == 1 時 有cij == 1。那么我們就稱此時的矩陣M`標識了G1 到G2子圖的一個同構。

初始化M的時候，遵循下面的原則：

如果G2的第 j 個節點的度大于或者等于G1的第 i 個節點的度（表示可能匹配但是不一定），則mij = 1。否則等于0。（此原則是針對無向圖，如果是對于有向圖則有出度和入度均要大于等于，對于節點可能有其他屬性的情況也是類似，保證G2的屬性或者條件強于G1即可）。

所以深度優先搜索的就是將M0深度遍歷找到所有的滿足條件（1）判定的矩陣。

深度優先搜索中，使用d來表示搜索中的層（第幾行），使用一個大小為p2的向量F{F1，F2，…F（x）…，F（p2）}（數組表示）來表示哪一列被使用了。比如F[2]==1表示在搜索中第二列被使用了，如果F[2]==0則表示沒被使用。同樣還使用一個大小為p1的向量H{H1，H2，……，H（p1）}來表示在哪一層使用了哪一列。H[d] = k表示在層d中使用了第k列。

除此之外，還需要一個三維矩陣來記錄每層變化過的M`，保證回溯的時候可以回到上一層。第一維長度和d大小一樣。二維三維即為M的維度。

Ullmann算法的提出者Ullmann的論文，比較早論文寫得挺難懂的。他的偽代碼有些需要改動。偽代碼如下：

step1 ? ??

construct ?M0，M=M0,d=0, H[0] = 0;

for element in F set element = 0

if ?m has a row that all zero ?return; (這一步可以放在refine里面)

?

step2 ? ??

if there are no value of j such ?that ?m[d][j] && F[j] = 0 ?then goto step7

matrixlist[d] = M

if d = 0 then k = H[0] else k = 0

?

step3 ? ? ?

if ?matrixlist[d][d][k] = 0 or?F[k] == 1

then ?if k < p2-1 then k+=1 and goto step3 else goto step7

else ?for all j != k set m[d][j] = 0;

?

step4 ? ? ?if d < p1 then goto step6 else ? ( H[d] = k and use condition(1) and giveoutput if an isomorphism is found )

?

step5 ? ??

if there is no j > k such that m[d][j] = 1 and F[j] = 0 then k += 1 and ?goto step7

else k += 1 and goto step3

?

step6 ? ?

?H[d] = k

F[k] = 1

d +=1

goto?step2

?

step7 ? ??

if d ==0 then terminate algorithm

if k < p2-1 then copy matrixlist[d] ?to M and goto step5

else ?d= d-1 ? ? k = H[d] ? ?F[k]=0?copy matrixlist[d] ?to M and goto step5

以上就是算法程序的偽代碼。具體實現還是需要自己動手。主要流程就是這樣的，缺少的就是condition（1）的判斷（包含矩陣的轉置和兩矩陣的乘法）。很簡單，自己加上。之后學習完refine procedure之后會再加上。暫時就這么多。

國內真心很少有這個問題的資料，一些論文都是應用子圖同構算法，極少有詳細講這些算法的。

摘要: 轉載請注明來自stanlysheng——talk is cheap, show me your code。http://www.cnblogs.com/stanly/?。謝謝。

轉載于:https://www.cnblogs.com/stanly/p/ullmann_algorithm.html

總結

以上是生活随笔為你收集整理的子图同构算法——Ullmann算法（1）不包含refine procedure的简单穷举算法。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。