# 图同构

## 定义

### 一般定义

${\displaystyle G}$  ${\displaystyle H}$  从图${\displaystyle G}$ 到图${\displaystyle H}$ 的同构映射${\displaystyle \sigma }$
${\displaystyle \sigma (a)=1}$

${\displaystyle \sigma (b)=6}$

${\displaystyle \sigma (c)=8}$

${\displaystyle \sigma (d)=3}$

${\displaystyle \sigma (g)=5}$

${\displaystyle \sigma (h)=2}$

${\displaystyle \sigma (i)=4}$

${\displaystyle \sigma (j)=7}$

## 图同构问题

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

### 计算复杂度

${\displaystyle \min _{P\in \{0,1\}^{n\times n},P^{T}P=I}\left\|G-PHP^{T}\right\|_{F}}$

• 子图同构(Subgraph Isomorphism)问题：给定图${\displaystyle G}$ 和图${\displaystyle H}$ ，图${\displaystyle G}$ 的节点数目小于图${\displaystyle H}$ ，问是否存在${\displaystyle H}$ 的某一子图(subgraph)，其与图${\displaystyle G}$ 同构

2015年，芝加哥大学教授、匈牙利裔计算机科学家宣布证明了图同构问题可以在准多项式(Quasi-polynomial)时间内求解[3]哈洛德·贺欧夫各特指出了文中的一处错误，随后Babai宣布修正了该错误并更新了论文[4]

## 参考文献

1. ^ László Babai. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. ICM 2018.
2. ^ Lyzinski, Vince, Information Recovery in Shuffled Graphs via Graph Matching, 2016,
3. ^ Babai, László, Graph Isomorphism in Quasipolynomial Time, 2015,
4. ^ Babai, László, Graph isomorphism update, January 9, 2017 [2018-10-28], （原始内容存档于2018-10-14）
5. ^ Luks, Eugene M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of computer and system sciences. 1982, 25 (1): 42––65.
6. ^ László Babai; D. Yu. Grigoryev; David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. Proceedings of the fourteenth annual ACM symposium on Theory of computing. 1982: 310––324.
7. ^ Whitney, Hassler. Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics. January 1932, 54 (1): 150–168. JSTOR 2371086. doi:10.2307/2371086. hdl:10338.dmlcz/101067.
8. ^ NAUTY -- Graph Isomorphism. [2018-10-28]. （原始内容存档于2018-03-04）.
9. ^ D. Conte; P. Foggia; C. Sansone; M. Vento. Thirty Years Of Graph Matching In Pattern Recognition. International journal of pattern recognition and artificial intelligence. 2004, 18 (3): 265––298.
10. ^ Lyzinski, Vince; Fishkind, Donniell; Fiori, Marcelo; Vogelstein, Joshua; Priebe, Carey; Sapiro, Guillermo. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis \& Machine Intelligence. 2016.
11. ^ Aflalo, Yonathan; Bronstein, Alexander; Kimmel, Ron. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences. 2015, 112 (10): 2942––2947.