VF2算法以步骤为例

Question

有人能用简单的单词解释VF2算法的图形同构的步骤吗？我正在学习这个算法,但没有一个有效的例子就很苛刻.有人能引导我正确的方向吗？谢谢.

Answer 1

我将尽力向您简要解释我之前对此问题的回答:

VF2算法的任何工作示例？

我将使用与我之前的答案中相同的示例:

上面的2个图是V和V'.(V'不在图中,但它是右边的那个)

图中描述了VF2算法.

一步步

我想知道V和V'是否同构.

我将使用以下符号:XV是V中的节点X.

在VF2算法中,我将尝试将V中的每个节点与V'中的节点进行匹配.

步骤1 :

我将空V与空V'匹配:它始终有效

第2步: 我可以将1V与1V',2V'或3V'匹配

我将1V与1V'匹配:它始终有效

第3步:

我可以匹配2V和2V'或3V'

我将2V与2V'匹配:它起作用,因为{1V 2V}和{1V'2V}是同构的

第4步 :

我尝试将3V与V'中的节点匹配:我不能!{如果在V'中节点3和2之间存在边缘,并且在3和1之间没有边缘,那么这是可能的)

所以我回到第2步

第5步:

我匹配2V和3V'

第6步:

与第4步相同

我回到第2步.步骤2中没有解决方案,我回到第1步

第7步:

我匹配1V和2V'

第8步:

我匹配2V和1V'

第9步:

我匹配3V和3V'

它工作我匹配{1V 2V 3V}与{2V'1V'3V'}

图是同构的.

如果我测试所有解决方案并且它永远不会工作,那么图形将不会是同构的.

希望这可以帮助

关于你关于"匹配"的问题,请看一下关于图同构的维基百科文章:

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

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

希望您能通过此图更好地理解此算法.