有人可以解释VF2算法图同构简单的话的步骤？我在学习这个算法，但它是严酷的没有工作的例子。有人可能会导致我的方向是正确的？谢谢你。

Can someone explain the steps of the VF2 algorithm for graph isomorphism in simple words? I am learning this algorithm, but it is harsh without a working example. Can someone lead me the right direction? Thank you.

推荐答案

我会尽量给你我的previous回答这个问题，一个快速的解释：

I will try to give you a quick explaination of my previous answer to this question :

Any VF2算法的工作例子吗？

我会用同样的例子，一个在我的previous答案：

I will use the same example as the one in my previous answer :

2的上述曲线图，为V和V'（V'是未在图中，但它是一个在右边）

The 2 graphs above are V and V' .(V' is not in the drawing but it's the one on the right)

的VF2算法在图中所描述

The VF2 algorithm is described in the graph.

我想知道，如果V和V'是同构的。

I want to know if V and V' are isomorphic.

我将使用以下符号：XV为V节点X

I will use the following notations : XV is the node X in V

在VF2 algoritm我会尽量V中的每个节点匹配了节点V'。

In the VF2 algoritm I will try to match each node in V with a node in V'.

第1步：

我配合空V'空五：它始终工作

I match empty V with empty V' : it always works

第2步： 我可以匹配1V与1V，2V或3V

step 2 : I can match 1V with 1V',2V' or 3V'

我匹配1V女巫1V：它始终工作

I match 1V witch 1V' : it always works

第3步：

我可以匹配2V具有2V或3V

I can match 2V with 2V' or 3V'

我匹配2V具有2V：它的工作原理，因为{1V 2V}和{1V2V}是同构的。

I match 2V with 2V' : it works because {1V 2V} and {1V' 2V} are isomorphic

第四步：

我尝试匹配3V与V'的一个节点：我不能！ {如果其为节点3和2中V'和3至1无边缘）

I try to match 3V with a node in V' : I cannot! {it would be possible if their was an edge between node 3 and 2 in V', and no edge between 3 and 1)

于是我回到步骤2

第五步：

我匹配2V与3V

步骤6：

相同的步骤4

我回到步骤2。有在步骤2中没有解决，我回到步骤1

I go back to step 2. there is no solution in step 2 , I go back to step 1

第7步：

我匹配1V与2V

第8步：

我匹配2V与1V

第9步：

我匹配3V电压为3V

它的工作原理我匹配{1V 2V 3V} {具有2V1V3V}

it works I matched {1V 2V 3V} with { 2V' 1V' 3V'}

该图是同构的。

如果我测试所有的解决方案，它从未工程图不会同构的。

If I test all the solution and it never works the graph would not be isomorphic.

希望这有助于

关于你的匹配的问题，看看维基百科的文章上图isomorphis：

About you're question on "matching", have a look at the wikipedia article on graph isomorphis :

http://en.wikipedia.org/wiki/Graph_isomorphism

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

this is a good example of a function f that matches graph G and H :

希望您能更好的理解这个算法，这个例子。

Hope you can better understand this algorithm with this illustration.