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

问题描述

我一直在读<一href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf">VF2算法寻找，如果两个图是同构的，但我莫名其妙地失踪大局。可能是因为我缺少这方面的相关背景，但我看到的是一堆，我需要在每一步使用，没有看到一个直观的理由来解释为什么步骤正在开展的规则。

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?

推荐答案

我不知道这就是你要找的，但VF2算法按照以下步骤。

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

让说你有2图：V和V'，并要匹配V配合V'

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

该算法走下来一棵树，在每一步尝试V的下一个元素匹配的V一个人，当你通过V的所有节点去你停止（当你发现一个叶）。

The algorithm go 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).

算法：

• 第一步：如同空图V'空V
。
• 第二步：尽量数学V中的一个节点与V中的一个节点
• ...
• 在第N步：尽量匹配V中的一个节点，在v一个新的节点，如​​果 你不能退一万步在树和尝试新的比赛中 previous一步......如果你不能再回去等等......
• ...
• 结束：当你发现叶，即当您完成所有的节点去 在V'或当您完成所有的树又没有找到一片树叶。

• First step : match empty V with empty graph V'.
• Second step : try to math 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 all tree without finding a leaf.

示例

下面是一个例子，该算法继续从左树的右

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

A＆LT; - > B是指V配合的V'节点B的比赛节点A

"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屋！