用于确定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!的大小(边数,在这种情况下是1s的数量)= B =>图的大小不是同构的
2. 对于A的每个顶点,计算其度数并在B中寻找具有相同度数且之前未匹配的匹配顶点.如果没有匹配=>图形不是同构的.
3. 现在我们无法快速证明A和B不同构,下一步是什么？是否正确尝试A中每一行的排列直到A匹配B？真的不确定这一个......

Answer 1

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

• 图同构问题

根据该页面,有许多特殊情况已经用有效的多项式时间解决方案解决,但最优解的复杂性仍然是未知的.

Answer 2

我的项目- Griso -在sf.net：http://sourceforge.net/projects/griso/有这样的描述：
Griso是用C ++编写，并根据我自己的算法中图同构测试工具。
在此页面上查看 Griso 的示例输入/输出：http ://funkybee.narod.ru/graphs.htm