凱萊圖

凱萊圖（英語：Cayley graph），也叫做凱萊著色圖，是將離散群的抽象結構畫出的一種圖。它的定義是凱萊定理（以阿瑟·凱萊命名）所暗含的。畫凱萊圖時，要選定群的一個生成元集合（通常有限），不同選法可能得到不同的凱萊圖。凱萊圖是組合群論與幾何群論的中心工具。

在兩個生成元a和b上的自由群的凱萊圖

定義

假設$G$是群，而$S$是G的生成集。凱萊圖$\Gamma =\Gamma (G,S)$，是如下構造的著色的有向圖：

• $G$的每個元素$g$對應一個頂點。換言之，圖$\Gamma$的頂點集合$V(\Gamma )$視為與$G$等同；
• $S$中每個生成元$s$，對應一種顏色$c_{s}$；
• 對於任何$g\in G,s\in S$，畫一條由元素$g$至$gs$的有向邊，染成$c_{s}$色。換言之，邊集合$E(\Gamma )$由形如$(g,gs)$的有序對構成，邊的顏色由$s\in S$確定。

在幾何群論中，集合$S$通常取為有限、對稱（即滿足$S=S^{-1}$），並且不包含這個群的單位元$e$。在這種情況下，凱萊圖是簡單無向圖：它的邊沒有方向（由對稱性），並且不包含自環（因為$e\notin S$）。

例子

• 假設$G=\mathbb {Z}$是無限循環群（即整數的加法群），而集合$S$由標準生成元$1$和它的逆元（用加法符號為$-1$）構成，則它的凱萊圖是無窮鏈。
• 類似地，如果$G=\mathbb {Z} _{n}$是$n$階循環群（模$n$的加法群），而$S$仍由$G$的標準生成元$1$與逆元$-1$構成，則凱萊圖是環圖$C_{n}$。
• 群的直積的凱萊圖（新生成集取為原生成集之笛卡爾積），是對應的凱萊圖的笛卡爾積。因此阿貝爾群$\mathbb {Z} ^{2}$，關於四個元素$(\pm 1,\pm 1)$組成的生成集的凱萊圖，是平面$\mathbb {R} ^{2}$上的無窮網格，而帶有類似的生成集的直積$\mathbb {Z} _{n}\times \mathbb {Z} _{m}$的凱萊圖，是環面上的$n$乘$m$有限網格。
• 二面體群$D_{4}$有群展示：$$\langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .$$左圖是關於兩個生成元$a$和$b$的凱萊圖，其中紅色箭頭表示左乘元素$a$（順時針旋轉$90^{\circ }$）。而因為元素$b$（左右反射）自反，所以表示左乘元素$b$的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有$8$個頂點、$8$條有向邊、$4$條無向邊。

  

  二面體群$D_{4}$關於兩個生成元$a$和$b$的凱萊圖。

  

  $D_{4}$關於兩個自反生成元的凱萊圖

  同一個群$D_{4}$，亦可畫出不同的凱萊圖，如右圖。$b$仍表示左右反射，而$c$則是關於主對角線的反射，以粉紅色線表示。由於兩個反射皆自反，右邊的凱萊圖完全無向。對應的群展示是$$\langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .$$
• 條目開頭的圖，是兩個生成元$a,b$上的自由群，關於生成集合$S=\{a,b,a^{-1},b^{-1}\}$的凱萊圖，而正中央的黑點，是單位元$e$。沿著邊向右走表示右乘$a$，而沿著邊向上走表示乘以$b$。因為自由群沒有關係，它的凱萊圖中沒有環。這個凱萊圖是證明巴拿赫-塔斯基悖論的關鍵。
• 右邊有離散海森堡群

  

  海森堡群的一部分（顏色僅為方便看清分層）

$$\left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}$$ 的凱萊圖。所用的三個生成元$X,Y,Z$，分別對應$(x,y,z)=(1,0,0),\ (0,1,0),\ (0,0,1)$。其關係為$Z=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY$，亦可從圖中看出。本群為非交換無窮群。雖然是三維空間，其凱萊圖的增長卻是$4$階的。

特徵

群$G$通過左乘作用在自身上（參見凱萊定理）。這個作用可以看作$G$作用在它的凱萊圖上。明確而言，一個元素$h\in G$映射一個頂點$g\in V(\Gamma )$到另一個頂點$hg\in V(\Gamma )$。凱萊圖的邊集合被這個作用所保存：邊$(g,gs)$變換成邊$(hg,hgs)$。任何群在自身上的左乘作用是簡單傳遞的，特別是凱萊圖是頂點傳遞的。事實上，反向的結論也成立，即有下列等價刻劃，稱為扎比杜西定理（英語：Sabidussi's Theorem）：

（無標記又無著色）有向圖$\Gamma$是群$G$的某個凱萊圖，當且僅當$G$可作為圖自同構（就是要保存邊的集合）作用在$\Gamma$上，且該作用簡單傳遞。

要從一個凱萊圖$\Gamma =\Gamma (G,S)$找回群$G$和生成集$S$，先選擇一個頂點$v_{1}\in V(\Gamma )$，標上群的單位元$e$。接著，對$\Gamma$的每個頂點$v$，$G$中有唯一元素將$v_{1}$變換到$v$，於是可以在$v$處標記該唯一元素。最後要確定$G$的哪個生成集$S$，產生凱萊圖$\Gamma$，而所求的$S$就是毗連$v_{1}$的頂點標記的集合。生成集合是有限（這是凱萊圖的共同假定）當且僅當這個圖是局部有限的（就是說每個頂點僅毗連於有限多條邊）。

基本性質

• 如果生成集合的成員$s$是自身的逆元，即$s=s^{-1}$，則它一般被表示為無向邊。
• 凱萊圖$\Gamma (G,S)$本質上依賴於如何選擇生成集$S$。例如，如果生成集合$S$有$k$個元素，則凱萊圖的每個頂點都有$k$條有向邊進入，$k$條有向邊外出。當生成集合$S$為對稱集，且有$r$個元素時，凱萊圖是$r$度的正則圖。
• 在凱萊圖中的環（「閉合路徑」）指示$S$的元素之間的關係。在群的凱萊複形此一更複雜的構造中，對應於關係的閉合路徑被用多邊形「填充」。
• 如果$f:G'\to G$是滿射群同態並且$G'$的生成集合$S'$的元素的像是不同的，則導出圖覆疊映射$${\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad$$這里的$S=f(S')$，特別是，如果群$G$有$k$個生成元，階均不為$2$，並且這些生成元和它們的逆元構成集合$S$，則該集合生成的自由群$F(S)$有到$G$的滿同態（商映射），故$\Gamma (G,S)$被自由群的凱萊圖覆蓋，即$2k$度的無限正則樹。
• 即使集合$S$不生成群$G$，仍可以構造圖$\Gamma (G,S)$。但是，此情況下，所得的圖並不連通。在這種情況下，這個圖的每個連通分支對應$S$所生成子群的一個陪集。
• 對於有限凱萊圖（視為無向），其頂點連通性等於這個圖的度的$2/3$。若生成集極小（即移除任一元素及其逆元，就不再生成整個群），則其頂點連通性等於度數。至於邊連通性，則在任何情況下皆等於度數。
• 群$G$的每個乘性特徵標$\chi$都給出$\Gamma (G,S)$鄰接矩陣的特徵向量。若$G$為交換群，則對應的特徵值為$\lambda _{\chi }=\sum _{s\in S}\chi (s).$特別地，平凡特徵標（將所有元素映至常數$1$）對應的特徵值，等於$\Gamma (G,S)$的度數，即$S$的元素個數。若$G$為交換群，則恰有$|G|$個特徵標，故已足以確定全部特徵值。

Schreier陪集圖

如果轉而把頂點作為固定子群$H$的右陪集，就得到了一個有關的構造Schreier陪集圖，它是陪集枚舉或Todd-Coxeter算法的基礎。

與群論的關係

研究圖的鄰接矩陣特別是應用譜圖理論的定理能洞察群的結構。

參見

• 群的生成集合
• 群的展示