VF2 算法的任何工作示例? [英] Any working example of VF2 algorithm?

问题描述

我一直在阅读 VF2 算法 用于查找两个图是否同构但不知何故错过了大局.可能是我错过了这方面的相关背景，但我所看到的只是一堆我需要在每个步骤中使用的规则，而没有看到为什么要执行这些步骤的直观解释.

从基本的谷歌搜索来看，这似乎被认为是查找两个图是否同构的事实上的算法之一，但由于某种原因，我无法找到一个足够简单的解释，可以在高层次上理解.或者这个算法有别的名字吗?

无论如何，有没有人知道该算法如何工作的任何运行示例?

解决方案

我不确定这就是您要查找的内容，但 VF2 算法如下进行.

假设您有 2 个图:V 和 V'，并且您想将 V 与 V' 匹配

算法沿着一棵树向下走，在每一步中，您都尝试将 V 的下一个元素与 V' 中的一个进行匹配，当您遍历 V' 中的所有节点时(当您找到一片叶子时)，您就停止了.

算法:

• 第一步:将空 V 与空图 V' 匹配.
• 第二步:尝试将V中的一个节点与V'中的一个节点进行匹配
• ...
• 第N步:尝试将V中的一个节点与V'中的一个新节点匹配，如果你不能在树中返回一步并在树中尝试新的匹配上一步......如果你不能再回去等等......
• ...
• END :当你找到一片叶子时，即当你遍历所有节点时在 V' 中，或者当你在没有找到叶子的情况下穿过整棵树时.

示例

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

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

希望我很清楚，这就是您要找的.

I have been reading the VF2 algorithm for finding if two graphs are isomorphic but am somehow missing the big picture. Could be that I am missing the relevant background in this area but all I see is a bunch of rules that I need to use at each step, without seeing an intuitive explanation for why the steps are being carried out.

From basic Googling, it appears that this is considered one of the de facto algorithms for finding if two graphs are isomorphic but for some reason I am unable to find an explanation that is simple enough to understand at a high level. Or is this algorithm known by a different name?

In any case, is anyone aware of any running examples of how this algorithm works?

解决方案

I am not sure that's what you're looking for, but the VF2 algorithm proceeds as below.

Let's say you have 2 graphs: V and V' and you want to match V with V'

The algorithm goes down a tree, at each step you try to match a next element of V with one of V' and you stop when you went through all the nodes in V' (when you find a leaf).

Algorithm:

• First step : match empty V with empty graph V'.
• Second step : try to match one node in V with one node in V'
• ...
• Nth step : try to match one node in V with one new node in V', if you cannot go back one step in the tree and try a new match in the previous step.. and if you cant go back again etc...
• ...
• END : when you find a leaf, i.e when you went through all the nodes in V' or when you went through the whole tree without finding a leaf.

Example

Here is a example, the algorithm proceeds from left to right of the tree.

"A <-> B" means Match node A of V with node B of V'

Hope I'm clear and that's what your looking for.

这篇关于VF2 算法的任何工作示例?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！