algorithm - VF2算法步骤举例

Question

有人能用简单的话解释一下图同构的 VF2 算法的步骤吗？我正在学习这个算法，但是没有一个可行的例子就很苛刻。有人可以引导我正确的方向吗？谢谢你。

Answer 1

我将尝试快速解释一下我之前对这个问题的回答：

VF2算法的任何工作示例？

我将使用与上一个答案中的示例相同的示例：

上面的两张图是V和V'。（V'不在图中，但它是右边的那个）

图中描述了 VF2 算法。

一步步

我想知道 V 和 V' 是否同构。

我将使用以下符号：XV 是 V 中的节点 X

在 VF2 算法中，我将尝试将 V 中的每个节点与 V' 中的节点进行匹配。

第1步 ：

我将空 V 与空 V' 匹配：它总是有效

第 2 步： 我可以将 1V 与 1V'、2V' 或 3V' 匹配

我将 1V 与 1V' 匹配：它总是有效

第 3 步：

我可以将 2V 与 2V' 或 3V' 匹配

我将 2V 与 2V' 匹配：它可以工作，因为 {1V 2V} 和 {1V' 2V} 是同构的

第4步 ：

我尝试将 3V 与 V' 中的节点匹配：我不能！{如果在 V' 中的节点 3 和 2 之间有一条边，并且在 3 和 1 之间没有边，这将是可能的）

所以我回到第2步

第 5 步：

我匹配 2V 和 3V'

第 6 步：

与第 4 步相同

我回到第 2 步。第 2 步没有解决方案，我回到第 1 步

第 7 步：

我匹配 1V 和 2V'

第 8 步：

我将 2V 与 1V 匹配'

第 9 步：

我将 3V 与 3V 匹配'

它有效我将 {1V 2V 3V} 与 { 2V' 1V' 3V'} 匹配

这些图是同构的。

如果我测试所有解决方案并且它永远不会工作，那么图形将不是同构的。

希望这可以帮助

---

关于您关于“匹配”的问题，请查看关于图同构的维基百科文章：

http://en.wikipedia.org/wiki/Graph_isomorphism

这是匹配图 G 和 H 的函数 f 的一个很好的例子：

希望您可以通过此插图更好地理解此算法。

Answer 2

提供了 VF 算法的高级概述：

程序匹配
    INPUT：一个中间状态s；初始状态 s0 有 M(s0)=
    OUTPUT：两个图之间的映射
    IF M(s) 覆盖 G2 的所有节点 THEN
        输出 M(s)
    别的
        计算包含在 M(s) 中的候选对的集合 P(s)
        FOREACH (n, m) P(s)
            如果 F(s, n, m) 那么
                计算通过将 (n, m) 添加到 M(s) 获得的状态 s´
                呼叫匹配
            万一
        结束 FOREACH
         恢复数据结构
    万一
结束程序