图的自同构群与对称性、可迁图

摘要: 图的群表示

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

图的同构

点同构

定义：$D = (V(D), E(D), \psi_{D})$ 和 $H = (V(H), E(H), \psi_{H})$ 为两个图，如果存在两个双射 $\theta: V(D) \to V(H)$，以及 $\phi: E(D) \to E(H)$ 使得 $\forall a \in E(D)$ 有：

$$\phi_{D}(a) = xy \Leftrightarrow \psi_{H}(\phi(a)) = \theta(x)\theta(y) \in E(H)$$

称 $D$ 与 $H$ (点)同构。记为 $G \cong H$。$\theta$ 称为 $D$ 与 $H$ 之间的同构映射。

若 $D, H$ 是简单图，则没有 $\psi$，于是仅需要存在映射 $\theta: V(D) \to V(H)$ 满足以下条件即可：

$$xy \in E(D) \Leftrightarrow \theta(x)\theta(y) \in E(H)$$

边同构

如果存在双射 $\phi: E(D) \rightarrow E(H)$，使得对任意相邻的两条边 $a, b \in E(D)$，$a$ 的终点是 $b$ 的起点 $\Leftrightarrow$ $\phi(a)$ 的终点是 $\phi(b)$ 的起点。

称 $D$ 和 $H$ 是边同构的，$\phi$ 称为边同构映射。

点同构与边同构的关系

定理：同构的两个非空简单有向图一定是边同构的。

---

证明 (构造)：

设 $D$ 和 $H$ 是两个非空简单有向图，$\theta$ 是 $D$ 到 $H$ 的同构映射(双射)。构造以下映射：

$$\theta^{* }: E(D) \rightarrow E(H)$$

使得对 $\forall a \in E(D)$ 有：

$$a = xy \Leftrightarrow \theta^{* }(a) = \theta(x)\theta(y)$$

由于 $\theta$ 是双射，$\theta^{* }$ 也是双射。

任取 $E(D)$ 中相邻的两条边，即 $\forall a, b \in E(D)$，其中 $a = xy, b = yz$，则 $\theta^{* }(a) = \theta(x)\theta(y) \in E(H), \theta^{* }(b) = \theta(y)\theta(z) \in E(H)$。因此 $\theta^{* }$ 是 $D$ 到 $H$ 的边同构映射。 $\Box$

映射 $\theta^{* }$ 称为由 $\theta$ 导出的边同构。

---

定理：边同构的两个非空连通简单有向图一定是点同构的。

---

证明 (构造)：

设 $D$ 和 $H$ 是两个非空简单有向图，$\phi$ 是 $D$ 到 $H$ 的边同构映射(双射)。

若 $a, b \in E(D)$ 为对称边，即 $a = xy, b = yx$，由于 $\phi(a)$ 的起点是 $\phi(b)$ 的终点，即若 $\phi(a) = uv$ 则 $\phi(b) = vu$，因此不妨设 $D$ 中没有对称边。

任取 $x_{0} \in V(D)$，由于 $D$ 是非空连通的简单图，因此 $x_{0}$ 不是孤立点，令：

$$E_{D}^{+}(x_{0}) = \{a_{1}, \cdots, a_{d^{+}}\}$$

其中 $a_{i}$ 的终点为 $x_{i}, i = 1,\cdots, d^{+}$。再令：

$$E_{D}^{-}(x_{0}) = \{a_{d^{+}+1}, \cdots, a_{d^{+}+d^{-}}\}$$

其中 $a_{j}$ 的起点为 $x_{j}, j = d^{+}+1,\cdots, d^{+}+d^{-}$。见下图：

若 $a_{ij} = (x_{i}, x_{j}) \in E(D)$，$i,j \neq 0$ 且 $i\neq j$。则 $\phi(a_{ij}) \in E(H)$ 且 $\phi(a_{i}) = b_{i}$，$\phi(a_{j}) = b_{j}$，$\phi(a_{ij}) = (y_{i}, y_{j})$，令：

$$D_{1} = D[x_{0}, x_{1}, \cdots, x_{d^{+} + d^{-}}] \\ H_{1} = H[y_{0}, y_{1}, \cdots, y_{d^{+} + d^{-}}] \\$$

定义：

$$\theta: V(D_{1}) \rightarrow V(H_{1})$$

使得 $\forall x_{i} \in V(D_{1})$ 有 $\theta(x_{i}) = y_{i}, i=0,1,\cdots,d^{+}+d^{-}$。则 $\theta$ 是 $D_{1}$ 到 $H_{1}$ 的同构映射。

若 $D_{1} = D$ 则我们已经找到了 $D$ 到 $H$ 的同构映射。

若 $D_{1}\neq D$。因为 $D$ 是连通的，所以存在 $x\in V(D) \setminus V(D_{1})$ 与 $V(D_{1})$ 中某些点相邻，任取其中一点 $x_{i} \in V(D_{1})$，显然 $x_{i}\neq x_{0}$。

不妨设 $(x, x_{i}) \in E(D)$，则 $\phi(x, x_{i}) \notin E(H_{1})$，由于 $x_{i}$ 是 $(x_{0}, x_{i})$ 和 $(x, x_{i})$ 的终点，所以 $y_{i}$ 是 $(y_{0}, y_{i}) = \phi((x_{0}, x_{i}))$ 和 $(y, y_{i})$ 的终点。

因而存在 $y \in V(H) \setminus V(H_{1})$ 使得 $\phi((x, x_{i})) = (y, y_{i}) \in E(H)$，令：

$$D_{2} = D[x_{0}, x_{1}, \cdots, x_{d^{+} + d^{-}}, x] \\ H_{2} = H[y_{0}, y_{1}, \cdots, y_{d^{+} + d^{-}}, y] \\$$

将同构映射 $\theta: V(D_{1}) \rightarrow V(H_{1})$ 补充定义 $\theta(x) = y$ 即得 $D_{2}$ 到 $H_{2}$ 的同构映射。

若 $D_{2} = D$ 则我们已经找到了 $D$ 到 $H$ 的同构映射。否则，反复进行以上过程，直到获得图 $D_{v-(d^{+}+d^{-})}=D$ 和 $H_{v-(d^{+} +d^{-})}=H$，同构映射 $\theta: V(D_{1})\rightarrow V(H_{1})$ 能被扩充到 $V(D)\rightarrow V(H)$。 $\Box$

---

自同构与图的群表示

$D$ 到自身的同构称为自同构。

定理：简单图 $D$ 的自同构映射集合在合成运算下构成群。

---

证明：

简单图 $D$ 的自同构 $\theta$ 是 $V(D)$ 上的置换，使得对 $\forall (x, y) \in E(D)$ 有 $(\theta(x), \theta(y)) \in E(D)$。记这样的置换集合为 $\Theta$。

对于 $V(D)$ 上的任意两个满足条件的置换 $\alpha, \beta \in \Theta$，以及 $x\in V(D)$，依置换的合成运算有：

$$(\alpha\beta(x)) = \alpha(\beta(x))$$

由代数中的结论，$\Theta$ 中的置换在置换合成运算下满足封闭性、结合律、有单位元、有逆元的性质，因此构成群。

---

简单图 $D$ 中每个自同构映射都是 $V(D)$ 上的一个置换 $\theta$，满足对 $\forall (x, y) \in E(D)$ 有 $(\theta(x), \theta(y)) \in E(D)$，这些置换在置换合成运算下构成群，称为图 $D$ 的自同构群，记为 $\mathrm{Aut}(D)$

例如：

• $\mathrm{Aut}(K_{n}^{* }) \cong S_{n}$：$n$ 阶完全有向图的自同构群为 $n!$ 阶对称群。
• $\mathrm{Aut}(\vec{C}_{n}) \cong C_{n}$：$n$ 阶有向圈的自同构群为 $n$ 阶循环群。

图的自同构群称为图的群表示。

类似地可以定义 $D$ 的边自同构和边自同构群。由前面的定理，$D$ 的自同构 $\theta$ 可以导出边自同构 $\theta^{* }$，因此 $\mathrm{Aut}(D)$ 可以导出 $D$ 的边自同构群，记为 $\mathrm{Aut^{* }}(D)$。

---

图的群表示可以借助群论的方法分析某些特殊的图，比如可迁图。

可以尝试证明以下结论：

(1) $D$ 是非空简单有向图，则 $\mathrm{Aut}(D) \cong \mathrm{Aut^{* }}(D) \Leftrightarrow D$ 至多含一个孤立点。

(2) 简单图 $D$ 和 $H$ 的邻接矩阵为 $\mathbf{A}(D)$ 和 $\mathbf{A}(H)$，则 $D \cong H \Leftrightarrow \mathbf{A}(D)$ 与 $\mathbf{A}(H)$ 置换相似。

(3) 简单图 $D$，$\mathrm{Aut}(D) \cong \mathrm{Aut}(D^{c})$

(4) 简单图 $D$，$|\mathrm{Aut}(D)| = v! \Leftrightarrow D \cong K_{v}^{* }$

(5) 同构于 $D$ 且不相等于 $D$ 的标号图数目为 $\frac{v!}{|\mathrm{Aut}(D)|}$

(6) 若 $D$ 是简单图且 $\mathbf{A}(D)$ 的特征根各异，则 $\mathrm{Aut}(D)$ 是 Abel 群。

---

图的对称性

点相似、点可迁图

$D$ 是简单图，$x_{1}, x_{2} \in V(D)$，若 $\exists \theta \in \mathrm{Aut}(D)$ 使得 $\theta(x_{1}) = x_{2}$ 则称 $x_{1}$ 和 $x_{2}$ 是点相似的。

这种相似关系是 $V(D)$ 上的等价关系。若 $D$ 每对定点都是相似的，称 $D$ 为点可迁(顶点传递)的。点可迁图一定是正则图。

循环图的定义

给定点集 $V = \{0,1,\cdots,n-1\}, n\geq 2$。在 $V$ 上可以定义循环图。

循环有向图的边集如下：

$$E = \{(i, j): \exists s \in S, j - i \equiv s \mod{n}\}, \quad S \subseteq V\setminus \{0\}$$

记为 $G(n; S)$。

$G(n; 1)$ 是有向圈 $\vec{C}_{n}$；$G(n;V\setminus \{0\})$ 为完全有向图 $K_{n}^{* }$

循环无向图的边集如下：

$$E = \{ij: \exists s \in S, |j-i| \equiv s \mod{n}\}, \quad S \subseteq \{1,2,\cdots,\left\lfloor\frac{n}{2}\right\rfloor\}$$

$G(n; \pm 1)$ 是无向圈 $C_{n}$；$G(n;\pm \{1,2,\cdots,\left\lfloor\frac{n}{2}\right\rfloor\}$ 为完全无向图 $K_{n}$。

循环图是点可迁的

对 $\forall i, j \in V, i < j$，轮换 $\pi = \{012\cdots n-1\} \in \mathrm{Aut}(G(n; S))$，有 $\pi^{j-i}(i) = j$。

边相似、边可迁图

$D$ 是简单图，$a_{1} = (x_{1}, y_{1}), a_{2} = (x_{2}, y_{2}) \in E(D)$，若 $\exists \phi \in \mathrm{Aut}(D)$ 使得 $\phi(x_{1}) = x_{2}, \phi(y_{1}) = y_{2}$，则称 $a_{1}, a_{2}$ 是边相似的。

这种边相似是 $E(D)$ 上的等价关系。若 $D$ 每对边都是相似的，称 $D$ 为边可迁(边传递)的。

边可迁图与点可迁图的关系

定理：$D$ 是边可迁图，且 $\delta(D) > 0$，则 $D$ 或者是点可迁的，或者是 2 部图。

---

证明：

设 $D$ 是边可迁图，$\delta(D) > 0$，设 $E(D) = \{a_{1}, a_{2}, \cdots, a_{\epsilon}\}$。

取 $a_{1} = (x, y) \in E(D)$，所以 $a_{1}$ 与 $D$ 中每条边都相似。于是，$\exists \theta_{1}, \cdots, \theta_{\epsilon} \in \mathrm{Aut(D)}$ 使得：

$$(\theta_{i}(x), \theta_{i}(y)) = a_{i} \in E(D), \quad i=1,2,\cdots,\epsilon$$

令：

$$V_{1} = \{\theta_{i}(x) \in V(D): i=1,2,\cdots,\epsilon\} \\ V_{2} = \{\theta_{i}(y) \in V(D): i=1,2,\cdots,\epsilon\}$$

由于 $D$ 没有孤立点，所以 $V(D) = V_{1} \cup V_{2}$。具体有以下两种情况：

(1) $V_{1} \cap V_{2} \neq \varnothing$，则 $D$ 是点可迁的。

任取 $u, w\in V(D)$，只需证明 $u, w$ 相似。

若 $v, w \in V_{1}$，因为 $D$ 是简单图，且 $\delta(D) > 0$，所以 $E_{D}^{+}(u) \neq \varnothing, E_{D}^{+}(w) \neq \varnothing$。

由于 $D$ 是边可迁的，所以对 $\forall a_{i} \in E_{D}^{+}(u)$，存在 $\theta_{i}$ 使得 $\theta_{i}(x) = u$，而且对 $\forall a_{j} \in E_{D}^{+}(w)$ 存在 $\theta_{j}$ 使得 $\theta_{j}(x) = w$，于是：

$$\theta_{j}\theta_{i}^{-1} \in \mathrm{Aut}(D), \quad \theta_{j}\theta_{i}^{-1}(u) = \theta_{j}(x) = w$$

即 $u$ 与 $w$ 相似。

若 $v, w \in V_{2}$，因为 $D$ 是简单图，且 $\delta(D) > 0$，所以 $E_{D}^{-}(u) \neq \varnothing, E_{D}^{-}(w) \neq \varnothing$。

由于 $D$ 是边可迁的，所以对 $\forall a_{i} \in E_{D}^{-}(u)$，存在 $\theta_{i}$ 使得 $\theta_{i}(y) = u$，而且对 $\forall a_{j} \in E_{D}^{-}(w)$ 存在 $\theta_{j}$ 使得 $\theta_{j}(y) = w$，于是：

$$\theta_{j}\theta_{i}^{-1} \in \mathrm{Aut}(D), \quad \theta_{j}\theta_{i}^{-1}(u) = \theta_{j}(y) = w$$

即 $u$ 与 $w$ 相似。

若 $u \in V_{1}, v \in V_{2}$，由于 $V_{1}\cap V_{2} \neq \varnothing$，所以 $\exists z \in V_{1} \cap V_{2}$，由前面对 $u, v$ 同时属于 $V_{1}$ 或 $V_{2}$ 的讨论，有 $u$ 和 $z$ 相似，$z$ 和 $w$ 相似，所以 $u$ 和 $w$ 相似。

(2) $V_{1} \cap V_{2} = \varnothing$，则 $D$ 是二部图。

令 $u, w \in V(D)$，若 $u, w$ 相邻，则 $\exists a_{k}\in E(D)$，使得 $u, w$ 是 $a_{k}$ 的两端点。

若 $a_{k} = (u, w)$，由于 $D$ 边可迁，所以存在 $\theta_{k}$，使得 $\theta_{k}(x) = u, \theta_{k}(y) = w$。由 $V_{1}, V_{2}$ 的定义，有 $u\in V_{1}, w\in V_{2}$。

若 $a_{k} = (w, u)$，由于 $D$ 边可迁，所以存在 $\theta_{k}$，使得 $\theta_{k}(x) = w \in V_{1}, \theta_{k}(y) = u \in V_{2}$。

所以 $D$ 是 2 部图。$\Box$

---