是否有任何簡單的例子來解釋ullmann算法

Question

我是學習圖論的新生。我現在學習（子）圖同構。有兩個重要算法：烏爾曼算法和vf2。

我已閱讀烏爾曼文件：一種子圖同構的算法。我也GOOGLE了它，谷歌給了我很多的應用程序，但我不明白算法的程序。

你能給我一個簡單的解釋嗎？

Answer 1

This answer給相關問題給出了Ullmann算法的源代碼。

These slides給出一個例子，但該算法的主要成分僅在幻燈片「Ullmann算法V2」中沒有提及。

所以我會舉一個例子。我們想知道GB是否有一個與GA同構的子圖。也就是說，我們將試圖將GA的頂點映射到GB的頂點，以便GA的邊緣映射到GB的邊緣。

注意，無論是原始論文和幻燈片採用了矩陣，稱爲M，但代碼沒有。這是因爲矩陣代表了與可能的分配[i]在代碼中表示的相同。如果第N個頂點可以被映射到GB的第N個頂點，那麼M [i] [j]恰好爲1。我將使用候選者（u）等來表示GB的頂點集合，其中可以映射GB的頂點u。

首先要觀察的是GA的頂點只能映射到GB的頂點至少要達到很大的程度。所以最初候選人（u）=候選人（v）= {a，b，e，f，g}，候選人（w）= {f}和z的候選人都是GB的頂點。

現在是我們第一次做「精煉M」程序，這是Ullmann算法的主要組成部分。也就是說，我們檢查每當GB的頂點x在GA的頂點y的候選中時，y的每個鄰居在x的鄰居中至少有一個候選。如果此檢查失敗，則我們從y的候選人中刪除x。我們檢查這些清除，直到沒有進一步的清除是可能的。

例如，h是z的候選者之一。然而，w是z的鄰居，但h（即g）的鄰居中沒有一個在候選人（w）= {f}中。因此，我們將永遠無法將z映射到h，因爲邊{w，z}將被映射到非邊。所以我們可以安全地從候選人（z）中刪除h。細化的結果是：候選者（u）=候選者（v）=候選者（z）= {a，e，g}和候選者（w）= {f}。

現在我們開始回溯。

我們首先嚐試將u映射到a。也就是說，我們設置候選人（u）= {a}並從其他候選集合中刪除。 Refine發現e和g都不是a的鄰居，所以我們從候選項（v）中刪除e和g。這使候選人（v）空着，所以我們從這個分支返回;撤消對候選人所做的更改。

現在，我們嘗試將u映射到e。再次，候選人（五）將最終空洞。

最後，我們嘗試將u映射到g，得到相同的結果。

我們得出結論，遺傳算法不是GB的子圖。無需嘗試所有8 * 7 * 6 * 5分配。

我忘了Ullmann最初是按照遞減的順序排列GA的頂點。但它不會有什麼區別 - 我們只會首先發現w只能映射到f，然後我們繼續在u上分支，得到的結果與我們獲得的結果完全相同。