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

Question

免责声明:我是图论的新手，我不确定这是否属于 SO、Math 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 ]   

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

这是我开始算法的方式(请原谅我缺乏数学严谨性)请帮助我完成/更正!

1. 如果 A 的大小(边数，在本例中为 1 的数量)!= B 的大小 => 图不是同构的
2. 对于 A 的每个顶点，计算其度数并在 B 中寻找具有相同度数的匹配顶点并且之前没有匹配。如果没有匹配 => 图不是同构的。
3. 既然我们无法快速证明 A 和 B 不是同构的，那么下一步是什么？在 A 匹配 B 之前尝试 A 中的每行排列是否正确？真的不确定这个...

Answer 1

这是一个很难解决的问题。有一个关于它的维基百科页面:

• Graph isomorphism problem

根据该页面，有许多特殊情况已通过有效的多项式时间解决方案解决，但最佳解决方案的复杂性仍然未知。