图同构

两个图如果只是顶点名称或画法不同，而顶点之间的连接结构完全相同，就称为同构。例如把一张网络图中的顶点重新编号、移动位置或弯曲边线，不会因此改变其抽象连接关系。

定义

对有限简单无向图 $G=(V_G,E_G)$ 与 $H=(V_H,E_H)$，若存在双射 $f:V_G\to V_H$，使任意不同顶点 $u,v$ 都满足 $$uv\in E_G⟺f(u)f(v)\in E_H,$$ 则称 $f$ 是图同构，记为 $G\cong H$。双向条件同时要求保留边和非边；双射保证每个顶点恰好对应一个顶点。

构造一个同构

令 $G$ 的顶点为 $1,2,3,4$，边为 $12,23,34$；令 $H$ 的顶点为 $a,b,c,d$，边为 $ab,bc,cd$。映射 $$f(1)=a,f(2)=b,f(3)=c,f(4)=d$$ 是双射，且三条边依次变为 $ab,bc,cd$。四个顶点各有六对不同顶点，三条边已一一对应，剩下三对非边也对应非边，故这是一个同构。即使将 $H$ 画成折线或将顶点位置打乱，结论不变。

顶点的摆放不同；按照给定映射，两图的边和非边均对应。

用不变量排除同构

同构图必然具有相同顶点数、边数和度数多重集：顶点的邻居经同构双射恰好变成像顶点的邻居，所以度数不变。连通分量的个数、每个给定长度的环数也不变。只要有一个这类量不同，就可以断定两个图不同构。

这些必要条件通常不是充分条件。例如六顶点环 $C_6$ 与两个互不相连的三角形都有六个顶点、六条边，每个顶点的度都为 2；但前者连通，后者有两个连通分量，因此不同构。单纯比较度数序列不足以给出肯定结论。

邻接矩阵

给两图分别选择顶点次序后，若同构对应于一个置换矩阵 $P$，它们的邻接矩阵满足 $$A_H=P^{𝖳}{A}_{G}P.$$ 这里 $P$ 按选定次序同时重排列和行。反过来，满足这个等式的置换矩阵给出一个同构；任意可逆矩阵产生的相似变换则不一定代表顶点置换。

图同构关注结构是否相同；同一个图到自身的同构叫图自同构。只要求边映为边而不要求双射与非边保持的映射，则属于图同态。