摘要: 图的群表示
【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings
图的同构
点同构
定义：D=(V(D),E(D),ψD) 和 H=(V(H),E(H),ψH) 为两个图，如果存在两个双射 θ:V(D)→V(H)，以及 ϕ:E(D)→E(H) 使得 ∀a∈E(D) 有：
ϕD(a)=xy⇔ψH(ϕ(a))=θ(x)θ(y)∈E(H)称 D 与 H (点)同构。记为 G≅H。θ 称为 D 与 H 之间的同构映射。
若 D,H 是简单图，则没有 ψ，于是仅需要存在映射 θ:V(D)→V(H) 满足以下条件即可：
xy∈E(D)⇔θ(x)θ(y)∈E(H)边同构
如果存在双射 ϕ:E(D)→E(H)，使得对任意相邻的两条边 a,b∈E(D)，a 的终点是 b 的起点 ⇔ ϕ(a) 的终点是 ϕ(b) 的起点。
称 D 和 H 是边同构的，ϕ 称为边同构映射。
点同构与边同构的关系
定理：同构的两个非空简单有向图一定是边同构的。
证明 (构造)：
设 D 和 H 是两个非空简单有向图，θ 是 D 到 H 的同构映射(双射)。构造以下映射：
θ∗:E(D)→E(H)使得对 ∀a∈E(D) 有：
a=xy⇔θ∗(a)=θ(x)θ(y)由于 θ 是双射，θ∗ 也是双射。
任取 E(D) 中相邻的两条边，即 ∀a,b∈E(D)，其中 a=xy,b=yz，则 θ∗(a)=θ(x)θ(y)∈E(H),θ∗(b)=θ(y)θ(z)∈E(H)。因此 θ∗ 是 D 到 H 的边同构映射。 ◻
映射 θ∗ 称为由 θ 导出的边同构。
定理：边同构的两个非空连通简单有向图一定是点同构的。
证明 (构造)：
设 D 和 H 是两个非空简单有向图，ϕ 是 D 到 H 的边同构映射(双射)。
若 a,b∈E(D) 为对称边，即 a=xy,b=yx，由于 ϕ(a) 的起点是 ϕ(b) 的终点，即若 ϕ(a)=uv 则 ϕ(b)=vu，因此不妨设 D 中没有对称边。
任取 x0∈V(D)，由于 D 是非空连通的简单图，因此 x0 不是孤立点，令：
E+D(x0)={a1,⋯,ad+}其中 ai 的终点为 xi,i=1,⋯,d+。再令：
E−D(x0)={ad++1,⋯,ad++d−}其中 aj 的起点为 xj,j=d++1,⋯,d++d−。见下图：
若 aij=(xi,xj)∈E(D)，i,j≠0 且 i≠j。则 ϕ(aij)∈E(H) 且 ϕ(ai)=bi，ϕ(aj)=bj，ϕ(aij)=(yi,yj)，令：
D1=D[x0,x1,⋯,xd++d−]H1=H[y0,y1,⋯,yd++d−]定义：
θ:V(D1)→V(H1)使得 ∀xi∈V(D1) 有 θ(xi)=yi,i=0,1,⋯,d++d−。则 θ 是 D1 到 H1 的同构映射。
若 D1=D 则我们已经找到了 D 到 H 的同构映射。
若 D1≠D。因为 D 是连通的，所以存在 x∈V(D)∖V(D1) 与 V(D1) 中某些点相邻，任取其中一点 xi∈V(D1)，显然 xi≠x0。
不妨设 (x,xi)∈E(D)，则 ϕ(x,xi)∉E(H1)，由于 xi 是 (x0,xi) 和 (x,xi) 的终点，所以 yi 是 (y0,yi)=ϕ((x0,xi)) 和 (y,yi) 的终点。
因而存在 y∈V(H)∖V(H1) 使得 ϕ((x,xi))=(y,yi)∈E(H)，令：
D2=D[x0,x1,⋯,xd++d−,x]H2=H[y0,y1,⋯,yd++d−,y]将同构映射 θ:V(D1)→V(H1) 补充定义 θ(x)=y 即得 D2 到 H2 的同构映射。
若 D2=D 则我们已经找到了 D 到 H 的同构映射。否则，反复进行以上过程，直到获得图 Dv−(d++d−)=D 和 Hv−(d++d−)=H，同构映射 θ:V(D1)→V(H1) 能被扩充到 V(D)→V(H)。 ◻
自同构与图的群表示
D 到自身的同构称为自同构。
定理：简单图 D 的自同构映射集合在合成运算下构成群。
证明：
简单图 D 的自同构 θ 是 V(D) 上的置换，使得对 ∀(x,y)∈E(D) 有 (θ(x),θ(y))∈E(D)。记这样的置换集合为 Θ。
对于 V(D) 上的任意两个满足条件的置换 α,β∈Θ，以及 x∈V(D)，依置换的合成运算有：
(αβ(x))=α(β(x))由代数中的结论，Θ 中的置换在置换合成运算下满足封闭性、结合律、有单位元、有逆元的性质，因此构成群。
简单图 D 中每个自同构映射都是 V(D) 上的一个置换 θ，满足对 ∀(x,y)∈E(D) 有 (θ(x),θ(y))∈E(D)，这些置换在置换合成运算下构成群，称为图 D 的自同构群，记为 Aut(D)
例如：
- Aut(K∗n)≅Sn：n 阶完全有向图的自同构群为 n! 阶对称群。
- Aut(→Cn)≅Cn：n 阶有向圈的自同构群为 n 阶循环群。
图的自同构群称为图的群表示。
类似地可以定义 D 的边自同构和边自同构群。由前面的定理，D 的自同构 θ 可以导出边自同构 θ∗，因此 Aut(D) 可以导出 D 的边自同构群，记为 Aut∗(D)。
图的群表示可以借助群论的方法分析某些特殊的图，比如可迁图。
可以尝试证明以下结论：
(1) D 是非空简单有向图，则 Aut(D)≅Aut∗(D)⇔D 至多含一个孤立点。
(2) 简单图 D 和 H 的邻接矩阵为 A(D) 和 A(H)，则 D≅H⇔A(D) 与 A(H) 置换相似。
(3) 简单图 D，Aut(D)≅Aut(Dc)
(4) 简单图 D，|Aut(D)|=v!⇔D≅K∗v
(5) 同构于 D 且不相等于 D 的标号图数目为 v!|Aut(D)|
(6) 若 D 是简单图且 A(D) 的特征根各异，则 Aut(D) 是 Abel 群。
图的对称性
点相似、点可迁图
D 是简单图，x1,x2∈V(D)，若 ∃θ∈Aut(D) 使得 θ(x1)=x2 则称 x1 和 x2 是点相似的。
这种相似关系是 V(D) 上的等价关系。若 D 每对定点都是相似的，称 D 为点可迁(顶点传递)的。点可迁图一定是正则图。
循环图的定义
给定点集 V={0,1,⋯,n−1},n≥2。在 V 上可以定义循环图。
循环有向图的边集如下：
E={(i,j):∃s∈S,j−i≡smodn},S⊆V∖{0}记为 G(n;S)。
G(n;1) 是有向圈 →Cn；G(n;V∖{0}) 为完全有向图 K∗n
循环无向图的边集如下：
E={ij:∃s∈S,|j−i|≡smodn},S⊆{1,2,⋯,⌊n2⌋}G(n;±1) 是无向圈 Cn；G(n;±{1,2,⋯,⌊n2⌋} 为完全无向图 Kn。
循环图是点可迁的
对 ∀i,j∈V,i<j，轮换 π={012⋯n−1}∈Aut(G(n;S))，有 πj−i(i)=j。
边相似、边可迁图
D 是简单图，a1=(x1,y1),a2=(x2,y2)∈E(D)，若 ∃ϕ∈Aut(D) 使得 ϕ(x1)=x2,ϕ(y1)=y2，则称 a1,a2 是边相似的。
这种边相似是 E(D) 上的等价关系。若 D 每对边都是相似的，称 D 为边可迁(边传递)的。
边可迁图与点可迁图的关系
定理：D 是边可迁图，且 δ(D)>0，则 D 或者是点可迁的，或者是 2 部图。
证明：
设 D 是边可迁图，δ(D)>0，设 E(D)={a1,a2,⋯,aϵ}。
取 a1=(x,y)∈E(D)，所以 a1 与 D 中每条边都相似。于是，∃θ1,⋯,θϵ∈Aut(D) 使得：
(θi(x),θi(y))=ai∈E(D),i=1,2,⋯,ϵ令：
V1={θi(x)∈V(D):i=1,2,⋯,ϵ}V2={θi(y)∈V(D):i=1,2,⋯,ϵ}由于 D 没有孤立点，所以 V(D)=V1∪V2。具体有以下两种情况：
(1) V1∩V2≠∅，则 D 是点可迁的。
任取 u,w∈V(D)，只需证明 u,w 相似。
若 v,w∈V1，因为 D 是简单图，且 δ(D)>0，所以 E+D(u)≠∅,E+D(w)≠∅。
由于 D 是边可迁的，所以对 ∀ai∈E+D(u)，存在 θi 使得 θi(x)=u，而且对 ∀aj∈E+D(w) 存在 θj 使得 θj(x)=w，于是：
θjθ−1i∈Aut(D),θjθ−1i(u)=θj(x)=w即 u 与 w 相似。
若 v,w∈V2，因为 D 是简单图，且 δ(D)>0，所以 E−D(u)≠∅,E−D(w)≠∅。
由于 D 是边可迁的，所以对 ∀ai∈E−D(u)，存在 θi 使得 θi(y)=u，而且对 ∀aj∈E−D(w) 存在 θj 使得 θj(y)=w，于是：
θjθ−1i∈Aut(D),θjθ−1i(u)=θj(y)=w即 u 与 w 相似。
若 u∈V1,v∈V2，由于 V1∩V2≠∅，所以 ∃z∈V1∩V2，由前面对 u,v 同时属于 V1 或 V2 的讨论，有 u 和 z 相似，z 和 w 相似，所以 u 和 w 相似。
(2) V1∩V2=∅，则 D 是二部图。
令 u,w∈V(D)，若 u,w 相邻，则 ∃ak∈E(D)，使得 u,w 是 ak 的两端点。
若 ak=(u,w)，由于 D 边可迁，所以存在 θk，使得 θk(x)=u,θk(y)=w。由 V1,V2 的定义，有 u∈V1,w∈V2。
若 ak=(w,u)，由于 D 边可迁，所以存在 θk，使得 θk(x)=w∈V1,θk(y)=u∈V2。
所以 D 是 2 部图。◻
