确定两个图是否同构的算法

Question

确定两个图是否同构的算法

algorithmlanguage-agnosticgraphgraph-theory

13

免责声明：我对图论完全是个新手，也不确定这个问题应该发在SO、Math SE等哪里。

给定两个邻接矩阵A和B，如何判断A和B是否同构。

例如，A和B不同构，而C和D同构。

A = [ 0 1 0 0 1 1     B = [ 0 1 1 0 0 0
      1 0 1 0 0 1           1 0 1 1 0 0
      0 1 0 1 0 0           1 1 0 1 1 0
      0 0 1 0 1 0           0 1 1 0 0 1
      1 0 0 1 0 1           0 0 1 0 0 1
      1 1 0 0 1 0 ]         0 0 0 1 1 0 ]

C = [ 0 1 0 1 0 1     D = [ 0 1 0 1 1 0
      1 0 1 0 0 1           1 0 1 0 1 0
      0 1 0 1 1 0           0 1 0 1 0 1
      1 0 1 0 1 0           1 0 1 0 0 1
      0 0 1 1 0 1           1 1 0 0 0 1
      1 1 0 0 1 0 ]         0 0 1 1 1 0 ]   

(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)

这是我开始设计算法的方式（请原谅我缺乏数学严谨性），请帮助我完善/纠正！

如果 A 的大小（边数，在这种情况下为 1 的数量）不等于 B 的大小 => 图形不同构
对于 A 的每个顶点，计算其度数并查找与其具有相同度数的未匹配的 B 中的顶点。如果没有匹配 => 图形不同构。
既然我们不能快速证明 A 和 B 不同构，下一步是什么？尝试对 A 中的每条线路进行排列直到 A 与 B 匹配是否正确？这个我真的不确定...

- Olivier Lalonde

我知道这种方法很糟糕，但你总可以采用蛮力法：保持A中的节点顺序，然后遍历B中节点标签的每个排列，直到它们匹配或没有更多的排列。当然，肯定有更好的方法... 像这样... - JoshD

1

看起来没有人知道任何多项式时间算法来识别图同构。因此，直接使用蛮力算法是可以的。尝试每个相同度数节点的排列等。 - phadej

4个回答

6

我的项目 - Griso - 在sf.net上：http://sourceforge.net/projects/griso/，它是一个用C++编写的图同构测试实用程序，基于我的自己的算法。
在这个页面上查看Griso的样例输入/输出：http://funkybee.narod.ru/graphs.htm。

- trg787

0

嗯，通过以下方法很容易快速判断它们不是同构的。


areIsomorphic(G1, G2):
      if(G1.num_verticies != G2.num_verticies)
              return False
       if(G1.num_total_edges != G2.num_total_edges)
              return False
      for each vertex v in G1:
            if( G2.find(v).edges != v.edges):
                     return False;
        //尝试在图G1中找到一个在G2中不存在的属性。
        //使用一种启发式方法。例如- 尝试找到非互相邻的集合。

- Alex Spencer

0

通常来说，证明两个图同构并不是一项简单的任务。因此，我们必须考虑一些同构图的特性。也就是说，如果这些特性被满足，那么这些图就是同构的。如果给定的图不满足这些特性，那么我们可以说它们不是同构图。

特性：当且仅当它们的顶点按照某种顺序排列时，两个图的邻接矩阵相等，那么它们就是同构的。

基于上述特性，我们可以判断给定的图是否同构。为了检查这个特性，我们需要进行一些矩阵变换操作。

- Sushant

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

这是一个相当难以解决的问题。有一个维基百科页面讨论了它:

图同构问题

根据该页面，已经有一些特殊情况得到了高效的多项式时间解决方案，但最优解决方案的复杂度仍然未知。