跳至內容

凱萊圖

維基百科,自由的百科全書
在兩個生成元ab上的自由群的凱萊圖

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

定義

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

  • 的每個元素對應一個頂點。換言之,圖的頂點集合視為與等同;
  • 中每個生成元,對應一種顏色
  • 對於任何,畫一條由元素有向邊,染成色。換言之,邊集合由形如的有序對構成,邊的顏色由確定。

在幾何群論中,集合通常取為有限、對稱(即滿足),並且不包含這個群的單位元。在這種情況下,凱萊圖是簡單無向圖:它的邊沒有方向(由對稱性),並且不包含自環(因為)。

例子

  • 假設是無限循環群(即整數的加法群),而集合由標準生成元和它的逆元(用加法符號為)構成,則它的凱萊圖是無窮鏈英語Path graph
  • 類似地,如果循環群(模的加法群),而仍由的標準生成元與逆元構成,則凱萊圖是環圖
  • 群的直積的凱萊圖(新生成集取為原生成集之笛卡爾積),是對應的凱萊圖的笛卡爾積英語Cartesian product of graphs。因此阿貝爾群,關於四個元素組成的生成集的凱萊圖,是平面上的無窮網格,而帶有類似的生成集的直積的凱萊圖,是環面上的有限網格。
  • 二面體群群展示左圖是關於兩個生成元的凱萊圖,其中紅色箭頭表示左乘元素(順時針旋轉)。而因為元素(左右反射)自反,所以表示左乘元素的藍色線是無方向的,故左圖混合了有向邊與無向邊:它有個頂點、有向邊條無向邊。
    二面體群關於兩個生成元的凱萊圖。
    關於兩個自反生成元的凱萊圖
    同一個群,亦可畫出不同的凱萊圖,如右圖。仍表示左右反射,而則是關於主對角線的反射,以粉紅色線表示。由於兩個反射皆自反,右邊的凱萊圖完全無向。對應的群展示是
  • 條目開頭的圖,是兩個生成元上的自由群,關於生成集合的凱萊圖,而正中央的黑點,是單位元。沿著邊向右走表示右乘,而沿著邊向上走表示乘以。因為自由群沒有關係,它的凱萊圖中沒有。這個凱萊圖是證明巴拿赫-塔斯基悖論的關鍵。
  • 右邊有離散海森堡群
    海森堡群的一部分(顏色僅為方便看清分層)

的凱萊圖。所用的三個生成元,分別對應。其關係為,亦可從圖中看出。本群為非交換無窮群。雖然是三維空間,其凱萊圖的增長英語Growth rate (group theory)卻是階的。[來源請求]

特徵

通過左乘作用在自身上(參見凱萊定理)。這個作用可以看作作用在它的凱萊圖上。明確而言,一個元素映射一個頂點到另一個頂點。凱萊圖的邊集合被這個作用所保存:邊變換成邊。任何群在自身上的左乘作用是簡單傳遞的,特別是凱萊圖是頂點傳遞英語Vertex-transitive graph的。事實上,反向的結論也成立,即有下列等價刻劃,稱為扎比杜西定理(英語:Sabidussi's Theorem):

(無標記又無着色)有向圖是群的某個凱萊圖,當且僅當可作為圖自同構(就是要保存邊的集合)作用在上,且該作用簡單傳遞。[1]

要從一個凱萊圖找回群和生成集,先選擇一個頂點,標上群的單位元。接著,對的每個頂點中有唯一元素將變換到,於是可以在處標記該唯一元素。最後要確定的哪個生成集,產生凱萊圖,而所求的就是毗連的頂點標記的集合。生成集合是有限(這是凱萊圖的共同假定)當且僅當這個圖是局部有限的(就是說每個頂點僅毗連於有限多條邊)。

基本性質

  • 如果生成集合的成員是自身的逆元,即,則它一般被表示為無向邊
  • 凱萊圖本質上依賴於如何選擇生成集。例如,如果生成集合個元素,則凱萊圖的每個頂點都有有向邊進入,條有向邊外出。當生成集合為對稱集,且有個元素時,凱萊圖是度的正則圖
  • 在凱萊圖中的(「閉合路徑」)指示的元素之間的關係。在群的凱萊複形此一更複雜的構造中,對應於關係的閉合路徑被用多邊形「填充」。
  • 如果滿射群同態並且的生成集合的元素的像是不同的,則導出圖覆疊英語Covering graph映射這里的,特別是,如果群個生成元,階均不為,並且這些生成元和它們的逆元構成集合,則該集合生成的自由群有到的滿同態(商映射),故被自由群的凱萊圖覆蓋,即度的無限正則
  • 即使集合不生成群,仍可以構造圖。但是,此情況下,所得的圖並不連通。在這種情況下,這個圖的每個連通分支對應所生成子群的一個陪集。
  • 對於有限凱萊圖(視為無向),其頂點連通性等於這個圖的。若生成集極小(即移除任一元素及其逆元,就不再生成整個群),則其頂點連通性等於度數。[2]至於邊連通性,則在任何情況下皆等於度數。[3]
  • 的每個乘性特徵標英語Multiplicative character都給出鄰接矩陣特徵向量。若為交換群,則對應的特徵值特別地,平凡特徵標(將所有元素映至常數)對應的特徵值,等於的度數,即的元素個數。若為交換群,則恰有個特徵標,故已足以確定全部特徵值。

Schreier陪集圖

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

與群論的關係

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

參見

注釋

  1. ^ Sabidussi, Gert. On a class of fixed-point-free graphs [論一類無不動點的圖]. Proceedings of the American Mathematical Society. October 1958, 9 (5): 800–4. JSTOR 2033090. doi:10.1090/s0002-9939-1958-0097068-7可免費查閱 (英語). 
  2. ^ Babai, L. Technical Report TR-94-10. University of Chicago. 1996. 存档副本. [2010-08-29]. (原始內容存檔於2010-06-11). 
  3. ^ 見定理3.7,Babai, László. 27. Automorphism groups, isomorphism, reconstruction [第27章:自同構群、同構、重構] (PDF). Graham, Ronald L.; Grötschel, Martin; Lovász, László (編). Handbook of Combinatorics [組合手冊] 1. Elsevier. 1995: 1447–1540 [2021-09-29]. ISBN 9780444823465. (原始內容存檔於2021-04-22).