Cayley圖

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

基本介紹

• 中文名：Cayley圖
• 外文名：Cayley graph
• 別稱：凱萊圖

定義

假設，是群而，是生成集。凱萊圖，是如下構造的著色的有向圖。

，每個元素，指派一個頂點：，的頂點集合，同一於。

，的每個生成元，指派一種顏色。

對於任何，對應於元素，和，的頂點用顏色，的有向邊連線。因此邊集合，由形如，的有序對構成，帶著提供的顏色。

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

例子

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

圖1.二面體群D4在兩個生成元a和b上的凱萊圖。

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

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

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

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

特徵

群通過左乘作用在自身上（參見凱萊定理）。這個作用可以看作作用在它的凱萊圖上。明顯的，一個元素映射一個頂點到頂點。凱萊圖的邊集合被這個作用所保存：邊變換成邊。任何群在自身上的左乘作用是簡單傳遞的，特別是凱萊圖是頂點傳遞的。這導致了凱萊圖的下列特徵：

圖是群的凱萊圖，若且唯若它通過圖自同構許可的簡單傳遞作用（就是保存邊的集合）。

要從一個凱萊圖恢復群和生成集，選擇一個頂點並標記上這個群的單位元。接著對每個的頂點標記上變換到的的唯一元素。產生為凱萊圖的的生成元的集合是毗連到選擇的頂點的頂點的標記的集合。生成集合是有限（這是凱萊圖的共同假定）若且唯若這個圖是局部有限的（就是說每個頂點毗連與有限多個邊）。

基本性質

如果生成集合的成員是自身的逆元，即，則它一般被表示為無向邊。

凱萊圖本質上依賴於生成元的集合的選擇方式。例如，如果生成集合有個元素，則凱萊圖的每個頂點都有個進入和個外出的有向邊。在有個元素的對稱生成集合的情況下，凱萊圖是度的正則圖。

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

如果是滿射群同態並且的生成集合的元素的像是不同的，則它引發一個圖的覆蓋

這裡的。

特別是，如果群有個生成元，都有不是2的階，並且這些生成元和它們的逆元構成集合，則凱萊圖由對應於在相同生成集合的自由群的度無限正則樹所覆蓋。

圖可以被構造即使集合不生成群。但是，它是連通的並不被認為是凱萊圖。在這種情況下，這個圖的每個連通部件表示一個生成子群的陪集。

對於被認為是無向的凱萊圖，頂點連通性等於這個圖的度。

陪集圖

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

與群論的關係

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

參見

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