凱萊圖

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

定義 

假設是群，而是G的生成集。凱萊圖，是如下構造的著色的有向圖：
 的每個元素對應一個頂點。換言之，圖的頂點集合視為與等同；
 中每個生成元，對應一種顏色；
 對於任何，畫一條由元素至的有向邊，染成色。換言之，邊集合由形如的有序對構成，邊的顏色由確定。

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

例子 

 假設是無限循環群（即整數的加法群），而集合由標準生成元和它的逆元（用加法符號為）構成，則它的凱萊圖是。
 類似地，如果是階循環群（模的加法群），而仍由的標準生成元與逆元構成，則凱萊圖是環圖。
 群的直積的凱萊圖（新生成集取為原生成集之笛卡爾積），是對應的凱萊圖的。因此阿貝爾群，關於四個元素組成的生成集的凱萊圖，是平面上的無窮網格，而帶有類似的生成集的直積的凱萊圖，是環面上的乘有限網格。
 二面體群有群展示：左圖是關於兩個生成元和的凱萊圖，其中紅色箭頭表示左乘元素（順時針旋轉）。而因為元素（左右反射）自反，所以表示左乘元素的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有個頂點、條有向邊、條無向邊。同一個群，亦可畫出不同的凱萊圖，如右圖。仍表示左右反射，而則是關於主對角線的反射，以粉紅色線表示。由於兩個反射皆自反，右邊的凱萊圖完全無向。對應的群展示是
 條目開頭的圖，是兩個生成元上的自由群，關於生成集合的凱萊圖，而正中央的黑點，是單位元。沿著邊向右走表示右乘，而沿著邊向上走表示乘以。因為自由群沒有關係，它的凱萊圖中沒有環。這個凱萊圖是證明巴拿赫-塔斯基悖论的關鍵。
右邊有離散海森堡群 

的凱萊圖。所用的三個生成元，分別對應。其關係為，亦可從圖中看出。本群為非交換無窮群。雖然是三維空間，其凱萊圖的卻是階的。

特征 

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

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

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

基本性質 

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

Schreier陪集圖 

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

與群論的關係 

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

參見 

 群的生成集合
 群的展示

注釋 

群論
置換群
图