VF2算法步骤及示例

Question

有人能用简单的话解释一下VF2算法在图同构中的步骤吗？我正在学习这个算法，但没有工作示例很困难。有人能给我指点方向吗？谢谢。

- Abdul Samad

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的很好的例子：

希望这个示例可以帮助您更好地理解这个算法。

- Ricky Bobby

---

谢谢您的解释，但我不理解匹配的含义，比如在第二步中，您写道：“我将1V与1V'匹配：它总是有效的”，但是1V和1V'具有不同的度数，如何才能成功地将它们匹配起来呢？请问您能否进一步说明节点匹配的确切含义？我的意思是，应该满足哪些条件，我们才能说图1中的节点已经成功地与图2中的某个节点匹配了。 - Abdul Samad

你能告诉我如何将一个节点与其他节点匹配吗？我的意思是什么是匹配，或者如果有其他人可以解释一下这个点。 - Abdul Samad

@AbdulSamad 匹配就像选择一个函数 f:G=(V,E)->G'=(V',E')，使得对于 G 中的任何节点或边缘中的任何点返回 G' 中的新节点和边缘。如果不清楚，我稍后会在今天有时间时为您澄清。 - Ricky Bobby

@AbdulSamad，我编辑了我的帖子以说明所谓的匹配意味着什么。如果你还有任何问题，请不要犹豫问我。 - Ricky Bobby

@RickyBobby "我将2V与2V'匹配：这是有效的，因为{1V 2V}和{1V' 2V}是同构的"。你的意思是说{1V 2V}和{1V' 2V'}是同构的吗？因为{1V' 2V}甚至不在同一个图中，所以它们之间没有边缘。 - Zyoo

Answer 2

提供VF算法的高级概述：

过程 匹配(s) 输入：中间状态s；初始状态s0具有M（s0）= 输出：两个图之间的映射 如果M（s）涵盖G2的所有节点，则 输出M（s） 否则 计算对候选包含在M（s）中的对P（s） 对于P（s）中的每个（n，m） 如果F（s，n，m），则 计算通过将（n，m）添加到M（s）中而获得的状态s´ 调用Match（s） 结束如果 循环结束 恢复数据结构 结束如果 结束过程

- Adam