算法确定2图是同构 [英] Algorithm for determining if 2 graphs are isomorphic

问题描述

免责声明：我在图论总新手，我不知道这是否属于对SO，数学SE等

。

由于2的邻接矩阵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]

（对不起，这个丑陋的符号，我不是很清楚如何借鉴矩阵的SO）
 

下面是如何我开始我的算法（原谅我缺乏数学的严谨性的），请帮助我完成/正确的！

1. 如果A的尺寸（边数，在此情况下1秒的量）！=乙的大小=>图不同构
2. 对于A的每个顶点，计算其程度和查找匹配的顶点B中具有相同程度的和的是不早匹配。如果没有匹配=>图是不是同构的。
3. 现在，我们不能很快证明，A和B是不是同构的，有什么下一步？ 难道是正确的试线，每次改变一个，直到比赛B'真不知道这样的产品......

解决方案

这是一个非常难以解决的问题。有一个关于它的维基百科页面：

• 图同构问题

据该网页有一些特殊情况已经解决了高效的多项式时间解，但最优解的复杂性仍是未知。

Disclaimer: I'm a total newbie at graph theory and I'm not sure if this belongs on SO, Math SE, etc.

Given 2 adjacency matrices A and B, how can I determine if A and B are isomorphic.

For example, A and B which are not isomorphic and C and D which are isomorphic.

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)

Here's how I've started my algorithm (pardon my lack of mathematical rigor) please help me complete/correct!

1. If size (number of edges, in this case amount of 1s) of A != size of B => graphs are not isomorphic
2. For each vertex of A, count its degree and look for a matching vertex in B which has the same degree and was not matched earlier. If there is no match => graphs are not isomorphic.
3. Now that we cannot quickly prove that A and B are not isomorphic, what's the next step? Would it be correct try every permutation of lines in A until A matches B? Really not sure about this one...

解决方案

That's a quite difficult problem to solve. There is a Wikipedia page about it:

• Graph isomorphism problem

According to that page there are a number of special cases that have been solved with efficient polynomial time solutions, but the complexity of the optimal solution is still unknown.

这篇关于算法确定2图是同构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！