User:SandoClemento2014/图同构

图同构(Graph Isomorphism)描述的是图论中,两个之间的完全等价关系。在图论的观点下,两个同构的被当作同一个图来研究。

定义

只有节点数目相同(即同阶)的两个才有可能同构。两个简单图  称为是同构的,当且仅当存在一个将 的节点   映射到 的节点 一一对应 ,使得 中任意两个节点  相连接,当且仅当 中对应的两个节点  相连接。如果  是有向图,那么同构的定义中还进一步要求对于 中任意两个相连的节点  ,边 与它在 中对应的边 方向相同。类似地可以定义两个多重图的同构关系。

一个具体的例子如下,为方便起见,两图中对应节点被染成了相同的颜色:

    从图 到图 的同构映射 
     

 

 

 

 

 

 

 

要注意的一点是,在图论中,一幅图经常可以有多种不同的方式在纸上或屏幕上画出来,所以两个看起来很不同的图也可能是同构的。尤其当图的节点数比较大时,很难一眼从画出的图上判断它们是否同构。

图同构问题

计算机科学数学统计学中,图同构问题是复杂度理论研究中经常讨论的热点话题之一。图同构问题容易和图匹配问题混淆:

  • 判定图同构(Graph Isomorphism)问题:只需判断两个图之间是否是同构的,但如果同构的话,并不要求具体找出任何做成同构的对应关系
  • 图匹配(Graph Matching)问题:判断两个图是否同构,如果同构,找出至少一个使得两者做成同构的节点间的一一对应关系

严格地说,两个问题是不同的,显然后者是比前者更进一步的问题,但也有一些论文将两者混同并用Graph Isomorphism一词指代Graph Matching问题。迄今尚无人严格证明两者难度在P/NP意义下是相等的(要证明这一点,就必须证明第一个问题的答案可被多项式时间约化为第二个问题的答案,即:存在一个正常数 ,使得对于任何一个可以判定两个图是否同构的算法 ,若 输出的判定为真,那么在参考 输出的结果的基础上再花费至多 时间就可找出至少一个做成图同构的一一对应)。

计算复杂度

判定图同构(Graph Isomorphism)的计算复杂度是未知的,因此现在仅能被粗略地归类为NP图匹配(Graph Matching)问题的复杂度是NP困难。另有与两个问题相关的更进一步的问题:

  • 子图同构/匹配(Subgraph Isomorphism/Matching)问题:给定图 和图 ,图 的节点数目小于图 ,问是否存在 的某一子图(subgraph),其与图 同构,或更进一步地要求找出至少一个此种同构

无论是子图同构还是子图匹配都是NP完全问题。

2015年,芝加哥大学教授、匈牙利裔计算机科学家László Babai英语László Babai宣布证明了图同构问题可以在准多项式(Quasi-polynomial)时间内求解[1]Harald Helfgott英语Harald Helfgott指出了文中的一处错误,随后Babai宣布修正了该错误并更新了论文[2]

对于以下的特殊情形,图同构问题是可以多项式时间甚至快速求解的:


实用解法

目前最具代表性的实用解法是由澳大利亚计算机科学家Brendan McKay英语Brendan McKay提出的NAUTY[3],其对每一个图 估计其节点的一个标准索引排列(Canonical Indexing,或称Canonical Labeling),但标准索引可能非常耗时,而NAUTY算法通过对图的自同构性质的利用大大加快了标准索引的计算速度。

参考文献

  1. ^ Babai, László, Graph Isomorphism in Quasipolynomial Time, 2015, Bibcode:2015arXiv151203547B, arXiv:1512.03547  
  2. ^ Babai, László, Graph isomorphism update, January 9, 2017 
  3. ^ NAUTY -- Graph Isomorphism.