以实例VF2算法步骤 [英] VF2 algorithm steps with example
问题描述
有人可以解释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 :
<一个href="http://stackoverflow.com/questions/6743894/any-working-example-of-vf2-algorithm/6744603#6744603">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 :
<一个href="http://en.wikipedia.org/wiki/Graph_isomorphism">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.
这篇关于以实例VF2算法步骤的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
