User:SandoClemento2014/图同构

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

定义

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

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

图$G$	图$H$	从图$G$到图$H$的同构映射$\sigma$
		$\sigma (a)=1$ $\sigma (b)=8$ $\sigma (c)=8$ $\sigma (d)=3$ $\sigma (g)=5$ $\sigma (h)=2$ $\sigma (i)=4$ $\sigma (j)=7$

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

图同构问题

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

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

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

计算复杂度

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

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

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

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

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

• 树
• 平面图
• 区间生成图
• 置换生成图
• 循环对称图
• 以及当任意一个下面列举的描述图结构性特征的统计量被不随节点数增长的常数上限约束时，图同构问题可被多项式时间求解：
  • 图的树分解宽度
  • 亏格
  • 最大的节点度数
  • 图的邻接矩阵或任何一种拉普拉斯矩阵的特征值的最大重数

实用解法

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