VF2算法的任何工作示例？

Question

我一直在阅读VF2算法,以找出两个图是否同构,但不知何故错过了大图.可能是我错过了这个领域的相关背景,但我看到的是我需要在每一步使用的一系列规则,而没有看到为什么要执行这些步骤的直观解释.

从基本的谷歌搜索来看,这似乎被认为是一个事实上的算法,用于查找两个图是否同构,但由于某种原因,我无法找到一个简单到足以在高层次上理解的解释.或者这个算法是用不同的名称知道的？

在任何情况下,是否有人知道该算法如何工作的任何运行示例？

Answer 1

我不确定你正在寻找什么,但VF2算法如下所示.

假设您有2个图表:V和V'并且您希望将V与V匹配

算法沿着一棵树走下去,在每一步你尝试将V的下一个元素与V'中的一个匹配,当你通过V'中的所有节点时(当你找到一个叶子时)你就停止了.

算法:

• 第一步:将空V与空图V'匹配.
• 第二步:尝试用V'中的一个节点计算V中的一个节点
• ...
• 第N步:尝试将V中的一个节点与V'中的一个新节点匹配,如果你不能在树中返回一步并在上一步中尝试新的匹配...如果你不能再回去等...
• ...
• 结束:当你找到一片叶子时,即你经历了V'中的所有节点,或者当你通过所有树而没有找到叶子时.

例

这是一个例子,算法从树的左到右进行.

"A < - > B"表示将V的节点A与V'的节点B匹配

希望我很清楚,这就是你要找的东西.