查看“图同构”的源代码

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

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

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

{|class="wikitable" style="margin: 1em auto 1em auto"
! 图<math>G</math>
! 图<math>H</math>
! 从图<math>G</math>到图<math>H</math>的同构映射<math>\sigma</math>
|-
|style="padding-left:2em;padding-right:2em;"|[[File:Graph isomorphism a.svg|100px]]
|style="padding-left:1em;padding-right:1em;"|[[File:Graph isomorphism b.svg|210px]]
|align="center" style="background-color:white;"|<math>\sigma(a)=1</math>

<math>\sigma(b)=6</math>

<math>\sigma(c)=8</math>

<math>\sigma(d)=3</math>

<math>\sigma(g)=5</math>

<math>\sigma(h)=2</math>

<math>\sigma(i)=4</math>

<math>\sigma(j)=7</math>
|}

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

==图同构问题==
在[[计算机科学]]、[[数学]]和[[统计学]]中，图同构问题是[[时间复杂度|复杂度理论]]研究中经常讨论的热点话题之一。'''图同构问题'''容易和'''图匹配问题'''混淆：
* '''判定图同构(Graph Isomorphism)问题：'''只需判断两个图之间是否是同构的，但如果同构的话，并不要求具体找出任何做成同构的对应关系
* '''图匹配(Graph Matching)问题：'''判断两个图是否同构，如果同构，找出至少一个使得两者做成同构的节点间的一一对应关系
严格地说，两个问题是不同的，显然后者是比前者更进一步的问题，但也有一些论文将两者混同并用Graph Isomorphism一词指代Graph Matching问题。迄今尚无人严格证明两者难度在P/NP意义下是相等的(要证明这一点，就必须证明第一个问题的答案可被多项式时间约化为第二个问题的答案，即：存在一个正常数<math>d>0</math>，使得对于任何一个可以判定两个图是否同构的算法<math>{\cal J}</math>，若<math>{\cal J}</math>输出的判定为真，那么在参考<math>{\cal J}</math>输出的结果的基础上再花费至多<math>O(n^d)</math>时间就可找出至少一个做成图同构的一一对应)。

===计算复杂度===
'''判定图同构(Graph Isomorphism)'''的计算复杂度是未知的，因此现在仅能被粗略地归类为[[NP (复杂度)|NP]]<ref>{{cite conference |author=László Babai |title=Groups, Graphs, Algorithms: The Graph Isomorphism Problem |conference=ICM 2018}}</ref>；'''图匹配(Graph Matching)问题'''本身的复杂度同样是未知的，但在机器学习领域非常流行的一种约化版本将其视为[[NP困难]]的{{tsl|en|Quadratic assignment problem|QAP}}问题的特殊情形
: <math> \min_{P\in\{0,1\}^{n\times n},P^TP=I}\left\|  G-PHP^T \right\|_F </math>
其中<math>\|\cdot\|_F</math>表示矩阵的[[矩陣範數#弗罗贝尼乌斯範数|Frobenius模]]。该QAP约化相当于问：要求找到从<math>G</math>到<math>H</math>的一一映射，使得在此映射下两个图'''最相似'''。显然图匹配问题是该QAP问题的一种特殊情形，因为当两个图并不同构时，寻找两图间同构映射的尝试是没有意义的，但寻找两图间的一个最大化相似度的“最优映射”仍然是有意义的。尤其在当所给的数据并非图的精确观测而是被随机误差污染时，更常用该约化形式并予以近似求解<ref>{{citation |last1=Lyzinski | first1=Vince | title=Information Recovery in Shuffled Graphs via Graph Matching| arxiv=1605.02315| year=2016}}</ref>。另有与两个问题相关的更进一步的问题：
* '''子图同构(Subgraph Isomorphism)问题：'''给定图<math>G</math>和图<math>H</math>，图<math>G</math>的节点数目小于图<math>H</math>，问是否存在<math>H</math>的某一子图(subgraph)，其与图<math>G</math>同构
'''子图同构'''已被证明是[[NP完全]]问题。

2015年，[[芝加哥大学]]教授、匈牙利裔计算机科学家{{tsl|en|László Babai}}宣布证明了'''图同构问题'''可以在'''准多项式(Quasi-polynomial)'''时间内求解<ref>{{citation |last1=Babai |first1=László |title=Graph Isomorphism in Quasipolynomial Time |arxiv=1512.03547 | year=2015}}</ref>。[[哈洛德·贺欧夫各特]]指出了文中的一处错误，随后Babai宣布修正了该错误并更新了论文<ref>{{citation|last=Babai|first= László|url=http://people.cs.uchicago.edu/~laci/update.html|title=Graph isomorphism update|date=January 9, 2017}}</ref>。

对于以下的特殊情形，图同构问题是可以多项式时间甚至快速求解的：
* [[树 (图论)|树]]
* [[平面图 (图论)|平面图]]
* {{tsl|en|Interval graph|区间生成图}}
* {{tsl|en|Permutation graph|置换生成图}}
* {{tsl|en|Circulant graph|循环对称图}}
* 以及当'''任意一个'''下面列举的描述图结构性特征的统计量被不随节点数增长的常数上限约束时，图同构问题可被多项式时间求解：
** {{tsl|en|Tree decomposition|图的树分解}}的{{tsl|en|Treewidth||宽度}}
** [[亏格]]
** 最大的节点度数 (这被认为是图同构理论迄今为止取得的最重要突破性进展之一) <ref>{{cite journal |author1=Luks, Eugene M |title=Isomorphism of graphs of bounded valence can be tested in polynomial time |journal=Journal of computer and system sciences |date=1982 |volume=25 |issue=1 |pages=42--65}}</ref>
** 图的[[邻接矩阵]]或'''任何一种'''{{tsl|en|Laplacian matrix|拉普拉斯矩阵}}的特征值的[[特征值和特征向量#代数重次|最大重数]]<ref>{{cite journal |author1=László Babai |author2=D. Yu. Grigoryev |author3=David M. Mount |title=Isomorphism of graphs with bounded eigenvalue multiplicity |journal=Proceedings of the fourteenth annual ACM symposium on Theory of computing |date=1982 |pages=310--324}}</ref>

===实用解法===
与理论研究主要关注计算复杂度不同，对实用解法的研究主要关注具体应用中的实践计算速度。[[P/NP问题]]只关注时间复杂度中<math>n</math>的指数，而不关注其系数大小。即使一个算法是多项式时间的，它也可能因<math>n</math>的系数过大导致的速度太慢及/或数值上不稳定，而在实践中根本没有用处；反之，一个优秀的实用解法，即使不能保证是多项式时间的，在很多应用上也可能比一些多项式时间的解法快得多。

在图同构问题上，目前处于领先性能的实用解法是由澳大利亚计算机科学家{{tsl|en|Brendan McKay}}在1980年代提出的NAUTY<ref>{{cite web| url=https://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml|title=NAUTY -- Graph Isomorphism}}</ref>，其对每一个图<math>G</math>估计其节点的一个'''标准索引排列(Canonical Indexing，或称Canonical Labeling)'''。标准索引可以非常耗时，而NAUTY算法通过探索图的自同构性群的性质，对索引步骤进行剪枝，大大加快了标准索引的计算速度。NAUTY自从提出以来，成为了几乎每一篇研究图同构和图匹配问题实用解法的论文必定要进行比较的竞争对手。

其它流行的方法包括：各色[[启发式算法]]<ref>{{cite journal |author1=D. Conte |author2=P. Foggia |author3=C. Sansone |author4=M. Vento |title=Thirty Years Of Graph Matching In Pattern Recognition |journal=International journal of pattern recognition and artificial intelligence |date=2004 |volume=18 |issue=3 |pages=265--298}}</ref>；对QAP约化进行{{tsl|en|Semidefinite programming||SDP}}松弛<ref>{{cite journal |author1=Lyzinski, Vince |author2=Fishkind, Donniell |author3=Fiori, Marcelo |author4=Vogelstein, Joshua |author5=Priebe, Carey |author6=Sapiro, Guillermo |title=Graph matching: Relax at your own risk |journal=IEEE Transactions on Pattern Analysis \& Machine Intelligence |date=2016}}</ref><ref>{{cite journal |author1=Aflalo, Yonathan |author2=Bronstein, Alexander |author3=Kimmel, Ron |title=On convex relaxation of graph isomorphism |journal=Proceedings of the National Academy of Sciences |date=2015 |volume=112 |issue=10 |pages=2942--2947}}</ref>；近似计算图之间的某种不依赖于节点顺序的距离，例如图之间的[[编辑距离]]和[[cut distance]]等，这些距离的精确计算通常是[[NP困难]]的。

==参考文献==

[[Category:图论]]
[[Category:离散数学]]
[[Category:机器学习]]
[[Category:计算机科学中未解决的问题]]
[[Category:数学中未解决的问题]]