凱萊圖

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

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

定義

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

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

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

例子

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

  

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

  

  $D_4$關於兩個自反生成元的凱萊圖

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

  

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

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

特征

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

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

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

基本性質

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

Schreier陪集圖

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

與群論的關係

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

參見

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