複製鏈接
請複製以下鏈接發送給好友

Cayley圖

鎖定
數學中,Cayley圖,即凱萊圖,也稱作凱萊着色圖,是編碼離散羣的圖。它的定義是凱萊定理(以阿瑟·凱萊命名)所暗含的,並使用這個羣的特定的通常有限的生成元集合。它是組合羣論與幾何羣論的中心工具。
中文名
Cayley圖
外文名
Cayley graph
別    名
凱萊圖

Cayley圖定義

假設
,而
是生成集。凱萊圖
是如下構造的着色的有向圖
,每個元素
,指派一個頂點:
,的頂點集合
,同一於
,的每個生成元
,指派一種顏色
對於任何
,對應於元素
,和
,的頂點用顏色
,的有向邊連接。因此邊集合
,由形如
,的有序對構成,帶着
提供的顏色。
在幾何羣論中,集合
,通常被假定為有限的、“對稱的”也就是
,並且不包含這個羣的單位元。在這種情況下,凱萊圖是正常的:它的邊沒有方向並且不包含環路。 [1] 

Cayley圖例子

圖1 二面體羣D4在兩個生成元a和b上的凱萊圖。 圖1 二面體羣D4在兩個生成元a和b上的凱萊圖。
假設G=Z是無限循環羣,而集合S有標準生成元1和它的逆元(用加法符號為−1)構成,則它的凱萊圖是無窮鏈。
類似的,如果G=Zn是n階循環羣而S由兩個元素構成,G的標準生成元和它的逆元,則凱萊圖是環圖Cn
羣的直積的凱萊圖是對應的凱萊圖的笛卡爾積。因此帶有四個元素(±1, ±1)組成的生成集的阿貝爾羣Z的凱萊圖是在平面R上無窮網格,而帶有類似的生成集的直積Zn×Zm的凱萊圖是在環面上n乘m有限網格。
二面體羣D4在兩個生成元a和b上的凱萊圖列於右側。紅色箭頭表示左乘元素a。因此元素b是自我逆轉的,表示左乘元素b藍色線是無方向的。因此這個圖是混合的:它有8個頂點,8個有向邊,4個邊。羣D4的凱萊表可以從羣展示得出:
在對應於集合S= {a,b,a,b}的兩個生成元a,b上的自由羣的凱萊圖列出在文章開頭,這裏的e表示單位元。沿着邊向右走表示右乘a,而沿着變向上走表示乘以b。因為自由羣沒有關係,它的凱萊圖中沒有。這個凱萊圖是證明巴拿赫-塔斯基悖論的關鍵因素。 [2] 

Cayley圖特徵

通過左乘作用在自身上(參見凱萊定理)。這個作用可以看作
作用在它的凱萊圖上。明顯的,一個元素
映射一個頂點
到頂點
。凱萊圖的邊集合被這個作用所保存:邊
變換成邊
。任何羣在自身上的左乘作用是簡單傳遞的,特別是凱萊圖是頂點傳遞的。這導致了凱萊圖的下列特徵:
是羣
的凱萊圖,當且僅當它通過圖自同構許可
的簡單傳遞作用(就是保存邊的集合)。
要從一個凱萊圖
恢復羣
和生成集
,選擇一個頂點
並標記上這個羣的單位元。接着對每個
的頂點
標記上變換
的唯一元素。產生
為凱萊圖的
的生成元的集合
是毗連到選擇的頂點的頂點的標記的集合。生成集合是有限(這是凱萊圖的共同假定)當且僅當這個圖是局部有限的(就是説每個頂點毗連與有限多個邊)。 [2] 

Cayley圖基本性質

如果生成集合的成員
是自身的逆元,即
,則它一般被表示為無向邊。
凱萊圖
本質上依賴於生成元的集合
的選擇方式。例如,如果生成集合
個元素,則凱萊圖的每個頂點都有
個進入和
個外出的有向邊。在有
個元素的對稱生成集合
的情況下,凱萊圖是
度的正則圖
在凱萊圖中的(“閉合路徑”)指示在
的兩個元素之間的關係。在羣的凱萊復形的更精細構造中,對應於關係的閉合路徑被用多邊形“填充”。
如果
滿射羣同態並且
的生成集合
的元素的像是不同的,則它引發一個圖的覆蓋
這裏的
特別是,如果羣
個生成元,都有不是2的階,並且這些生成元和它們的逆元構成集合
,則凱萊圖
由對應於在相同生成集合的自由羣的
度無限正則所覆蓋。
可以被構造即使集合
不生成羣
。但是,它是連通的並不被認為是凱萊圖。在這種情況下,這個圖的每個連通部件表示一個
生成子羣的陪集。
對於被認為是無向的凱萊圖,頂點連通性等於這個圖的 [2] 

Cayley圖陪集圖

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

Cayley圖與羣論的關係

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

Cayley圖參見

參考資料
  • 1.    Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.
  • 2.    Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.