凱萊圖

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

• ${\displaystyle G}$，每個元素${\displaystyle g}$，指派一個頂點：${\displaystyle \Gamma }$，的頂點集合${\displaystyle V(\Gamma )}$，同一於${\displaystyle G}$，。
• ${\displaystyle S}$，的每個生成元${\displaystyle s}$，指派一種顏色${\displaystyle c_{s}}$，。
• 對於任何${\displaystyle g\in G,s\in S}$，對應於元素${\displaystyle g}$，和${\displaystyle gs}$，的頂點用顏色${\displaystyle c_{s}}$，的有向邊連接。因此邊集合${\displaystyle E(\Gamma )}$，由形如${\displaystyle (g,gs)}$，的有序對構成，帶著${\displaystyle s\in S}$提供的顏色。

在幾何群論中，集合${\displaystyle S}$，通常被假定為有限的、“對稱的”也就是${\displaystyle S=S^{-1}}$，并且不包含這個群的單位元。在這種情況下，凱萊圖是正常的圖：它的邊沒有方向并且不包含環路。

• 假設G = Z是無限循環群而集合S有標準生成元1和它的逆元（用加法符號為−1）構成，則它的凱萊圖是無窮鏈。

• 類似的，如果G = Z_n是n階循環群而S由兩個元素構成，G的標準生成元和它的逆元，則凱萊圖是環圖C_n。

• 群的直積的凱萊圖是對應的凱萊圖的笛卡爾積。因此帶有四個元素（±1, ±1）組成的生成集的阿貝爾群Z²的凱萊圖是在平面R²上無窮網格，而帶有類似的生成集的直積Z_n×Z_m的凱萊圖是在環面上n乘m有限網格。

二面體群D₄在兩個生成元a和b上的凱萊圖。

• 二面體群D₄在兩個生成元a和b上的凱萊圖列于右側。紅色箭頭表示左乘元素a。因此元素b是自我逆轉的，表示左乘元素b藍色線是無方向的。因此這個圖是混合的：它有8個頂點，8個有向邊，4個邊。群D₄的凱萊表可以從群展示得出：

${\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle }$。

• 在對應於集合S = {a, b, a⁻¹, b⁻¹}的兩個生成元a, b上的自由群的凱萊圖列出在文章開頭，這里的e表示單位元。沿著邊向右走表示右乘a，而沿著變向上走表示乘以b。因為自由群沒有關係，它的凱萊圖中沒有環。這個凱萊圖是證明巴拿赫-塔斯基悖论的關鍵因素。

群${\displaystyle G}$通過左乘作用在自身上（參見凱萊定理）。這個作用可以看作${\displaystyle G}$作用在它的凱萊圖上。明顯的，一個元素${\displaystyle h\in G}$映射一個頂點${\displaystyle g\in V(\Gamma )}$到頂點${\displaystyle hg\in V(\Gamma )}$。凱萊圖的邊集合被這個作用所保存：邊${\displaystyle (g,gs)}$變換成邊${\displaystyle (hg,hgs)}$。任何群在自身上的左乘作用是簡單傳遞的，特別是凱萊圖是頂點傳遞的。這導致了凱萊圖的下列特征：

圖${\displaystyle \Gamma }$是群${\displaystyle G}$的凱萊圖，當且僅當它通過圖自同構許可${\displaystyle G}$的簡單傳遞作用（就是保存邊的集合）。

要從一個凱萊圖${\displaystyle \Gamma =\Gamma (G,S)}$恢復群${\displaystyle G}$和生成集${\displaystyle S}$，選擇一個頂點${\displaystyle v_{1}\in V(\Gamma )}$并標記上這個群的單位元。接著對每個${\displaystyle \Gamma }$的頂點${\displaystyle v}$標記上變換${\displaystyle v_{1}}$到${\displaystyle v}$的${\displaystyle G}$的唯一元素。產生${\displaystyle \Gamma }$為凱萊圖的${\displaystyle G}$的生成元的集合${\displaystyle S}$是毗連到選擇的頂點的頂點的標記的集合。生成集合是有限（這是凱萊圖的共同假定）當且僅當這個圖是局部有限的（就是說每個頂點毗連與有限多個邊）。

• 如果生成集合的成員${\displaystyle s}$是自身的逆元，即${\displaystyle s=s^{-1}}$，則它一般被表示為無向邊。

• 凱萊圖${\displaystyle \Gamma (G,S)}$本質上依賴於生成元的集合${\displaystyle S}$的選擇方式。例如，如果生成集合${\displaystyle S}$有${\displaystyle k}$個元素，則凱萊圖的每個頂點都有${\displaystyle k}$個進入和${\displaystyle k}$個外出的有向邊。在有${\displaystyle r}$個元素的對稱生成集合${\displaystyle S}$的情況下，凱萊圖是${\displaystyle r}$度的正則圖。

• 在凱萊圖中的環（“閉合路徑”）指示在${\displaystyle S}$的兩個元素之間的關係。在群的凱萊複形的更精細構造中，對應於關係的閉合路徑被用多邊形“填充”。

• 如果${\displaystyle f:G'\to G}$是滿射群同態并且${\displaystyle G'}$的生成集合${\displaystyle S'}$的元素的像是不同的，則它引發一個圖的覆蓋

${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad }$這里的${\displaystyle S=f(S')}$，。

特別是，如果群${\displaystyle G}$有${\displaystyle k}$個生成元，都有不是2的階，并且這些生成元和它們的逆元構成集合${\displaystyle S}$，則凱萊圖${\displaystyle \Gamma (G,S)}$由對應於在相同生成集合的自由群的${\displaystyle 2k}$度無限正則樹所覆蓋。

• 圖${\displaystyle \Gamma (G,S)}$可以被構造即使集合${\displaystyle S}$不生成群${\displaystyle G}$。但是，它是連通的并不被認為是凱萊圖。在這種情況下，這個圖的每個連通部件表示一個${\displaystyle S}$生成子群的陪集。

• 對于被認為是無向的凱萊圖，頂點連通性等于這個圖的度。[1]

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

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

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