凱萊圖

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

在數學中，凱萊圖也叫做凱萊著色圖是編碼離散群的圖。它的定義是凱萊定理(以阿瑟·凱萊命名)所暗含的，并使用這個群的特定的通常有限的生成元集合。它是組合群論與幾何群論的中心工具。

定義 [编辑]

假設 $G \,$ 是群而 $S \,$ 是生成集。凱萊圖 $\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} \,$ ，并且不包含這個群的單位元。在這種情況下，凱萊圖是正常的圖: 它的邊沒有方向并且不包含環路。

例子 [编辑]

假設 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₄ 的凱萊表可以從群展示得出:

$\langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle$ 。

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

特征 [编辑]

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

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

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