凱萊圖

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

定義
假設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, a b = b a^3 \rangle. 左圖是關於兩個生成元a和b的凱萊圖，其中紅色箭頭表示左乘元素a（順時針旋轉90^\circ）。而因為元素b（左右反射）自反，所以表示左乘元素b的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有8個頂點、8條有向邊、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 \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)。任何群在自身上的左乘作用是簡單傳遞的，特別是凱萊圖是的。事實上，反向的結論也成立，即有下列等價刻劃，稱為扎比杜西定理（）：

（無標記又無着色）有向圖\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算法的基礎。

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

參見

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

注釋