VF2算法步骤举例

Question

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

Answer 1

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

PROCEDURE Match(s)
    INPUT: an intermediate state s; the initial state s0 has M(s0)=
    OUTPUT: the mappings between the two graphs
    IF M(s) covers all the nodes of G2 THEN
        OUTPUT M(s)
    ELSE
        Compute the set P(s) of the pairs candidate for inclusion in M(s)
        FOREACH (n, m) P(s)
            IF F(s, n, m) THEN
                Compute the state s´ obtained by adding (n, m) to M(s)
                CALL Match(s )
            END IF
        END FOREACH
         Restore data structures
    END IF
END PROCEDURE

Answer 2

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

VF2 算法的任何工作示例吗？

我将使用与我之前的答案中的示例相同的示例：

上面的 2 个图是 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

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

希望通过这张图你能更好地理解这个算法。