图的同构

两个图若"顶点名称不同但结构完全相同"，就称同构；同构是图论中"相等"的精确含义。

定义

图 $G=(V,E)$ 与 $G'=(V',E')$ 称为同构，若存在双射 $f:V\to V'$ 使得

$$\{u,v\}\in E\iff\{f(u),f(v)\}\in E'$$

$f$ 称为同构映射。

性质

同构保持一切由结构决定的量：顶点数、边数、度序列、连通性、圈长等，这些量称为同构不变量。

示例

顶点为 $\{a,b,c\}$ 的三角形与顶点为 $\{1,2,3\}$ 的三角形同构（任取双射即可）。

一般图的同构判定尚无多项式算法，实用中先用不变量排除，再借助图的矩阵表示逐对核对。