凱萊著色圖

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

## 定義

假設 $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}$ 有群展示：左圖是關於兩個生成元 $a$ 和 $b$ 的凱萊圖，其中紅色箭頭表示左乘元素 $a$ （順時針旋轉 $90^{\circ }$ ）。而因為元素 $b$ （左右反射）自反，所以表示左乘元素 $b$ 的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有 $8$ 個頂點、 $8$ 條有向邊、 $4$ 條無向邊。同一個群 $D_{4}$ ，亦可畫出不同的凱萊圖，如右圖。 $b$ 仍表示左右反射，而 $c$ 則是關於主對角線的反射，以粉紅色線表示。由於兩個反射皆自反，右邊的凱萊圖完全無向。對應的群展示是
* 條目開頭的圖，是兩個生成元 $a,b$ 上的自由群，關於生成集合 $S=\{a,b,a^{-1},b^{-1}\}$ 的凱萊圖，而正中央的黑點，是單位元 $e$ 。沿著邊向右走表示右乘 $a$ ，而沿著邊向上走表示乘以 $b$ 。因為自由群沒有關係，它的凱萊圖中沒有環。這個凱萊圖是證明巴拿赫 - 塔斯基悖論的關鍵。
* 右邊有離散海森堡群

的凱萊圖。所用的三個生成元 $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'$ 的元素的像是不同的，則導出圖覆疊映射這里的 $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 算法的基礎。

## 與群論的關係

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

## 參見

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

## 注釋