##### 图同构 - 图同构 - **图同构**是一种图论中的[[同态|同构]], 用于判断两个[[图]]在结构上是否相同, 即是否存在一种方式可以通过重新标记顶点使得两个图完全相同. 给定两个图 $G = (V_G, E_G)$ 和 $H = (V_H, E_H)$, 如果存在一个[[映射|双射]] $f: V_G \to V_H$, 使得 $(u, v) \in E_G \iff (f(u), f(v)) \in E_H$ 则称 $G$ 和 $H$ 是同构的. 判定两个图是否同构常常很复杂, 可以使用图的同构不变量进行初步筛选, 例如顶点数, 边数, 度数序列, 连通分量数等, 如果两个图的不变量不同, 则它们不同构