在兩個生成元a 和b 上的自由群 的凱萊圖 凱萊圖 (英語:Cayley graph ),也叫做凱萊著色圖 ,是將離散群 的抽象結構畫出的一種圖 。它的定義是凱萊定理 (以阿瑟·凱萊 命名)所暗含的。畫凱萊圖時,要選定群的一個生成元集合 (通常有限),不同選法可能得到不同的凱萊圖。凱萊圖是組合群論 與幾何群論 的中心工具。
假設 G {\displaystyle G} 是群 ,而 S {\displaystyle S} 是G的生成集 。凱萊圖 Γ = Γ ( G , S ) {\displaystyle \Gamma =\Gamma (G,S)} ,是如下構造的著色的有向圖 :
G {\displaystyle G} 的每個元素 g {\displaystyle g} 對應一個頂點 。換言之,圖 Γ {\displaystyle \Gamma } 的頂點集合 V ( Γ ) {\displaystyle V(\Gamma )} 視為與 G {\displaystyle G} 等同; S {\displaystyle S} 中每個生成元 s {\displaystyle s} ,對應一種顏色 c s {\displaystyle c_{s}} ; 對於任何 g ∈ G , s ∈ S {\displaystyle g\in G,s\in S} ,畫一條由元素 g {\displaystyle g} 至 g s {\displaystyle gs} 的有向邊 ,染成 c s {\displaystyle c_{s}} 色。換言之,邊集合 E ( Γ ) {\displaystyle E(\Gamma )} 由形如 ( g , g s ) {\displaystyle (g,gs)} 的有序對構成,邊的顏色由 s ∈ S {\displaystyle s\in S} 確定。 在幾何群論中,集合 S {\displaystyle S} 通常取為有限 、對稱(即滿足 S = S − 1 {\displaystyle S=S^{-1}} ),并且不包含這個群的單位元 e {\displaystyle e} 。在這種情況下,凱萊圖是简单無向圖 :它的邊沒有方向(由對稱性),并且不包含自環 (因為 e ∉ S {\displaystyle e\notin S} )。
假設 G = Z {\displaystyle G=\mathbb {Z} } 是無限循環群 (即整數的加法群),而集合 S {\displaystyle S} 由標準生成元 1 {\displaystyle 1} 和它的逆元(用加法符號為 − 1 {\displaystyle -1} )構成,則它的凱萊圖是無窮鏈 。 類似地,如果 G = Z n {\displaystyle G=\mathbb {Z} _{n}} 是 n {\displaystyle n} 階循環群 (模 n {\displaystyle n} 的加法群),而 S {\displaystyle S} 仍由 G {\displaystyle G} 的標準生成元 1 {\displaystyle 1} 與逆元 − 1 {\displaystyle -1} 構成,則凱萊圖是環圖 C n {\displaystyle C_{n}} 。 群的直積 的凱萊圖(新生成集取為原生成集之笛卡爾積),是對應的凱萊圖的笛卡爾積 。因此阿貝爾群 Z 2 {\displaystyle \mathbb {Z} ^{2}} ,關於四個元素 ( ± 1 , ± 1 ) {\displaystyle (\pm 1,\pm 1)} 組成的生成集的凱萊圖,是平面 R 2 {\displaystyle \mathbb {R} ^{2}} 上的無窮網格 ,而帶有類似的生成集的直積 Z n × Z m {\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}} 的凱萊圖,是環面 上的 n {\displaystyle n} 乘 m {\displaystyle m} 有限網格。 二面體群 D 4 {\displaystyle D_{4}} 有群展示 : ⟨ a , b | a 4 = b 2 = e , a b = b a 3 ⟩ . {\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .} 左圖是關於兩個生成元 a {\displaystyle a} 和 b {\displaystyle b} 的凱萊圖,其中紅色箭頭表示左乘元素 a {\displaystyle a} (順時針旋轉 90 ∘ {\displaystyle 90^{\circ }} )。而因為元素 b {\displaystyle b} (左右反射)自反 ,所以表示左乘元素 b {\displaystyle b} 的藍色線是無方向的,故左圖混合了有向邊與無向邊:它有 8 {\displaystyle 8} 個頂點、 8 {\displaystyle 8} 條有向邊 、 4 {\displaystyle 4} 條無向邊。二面體群 D 4 {\displaystyle D_{4}} 關於兩個生成元 a {\displaystyle a} 和 b {\displaystyle b} 的凱萊圖。 D 4 {\displaystyle D_{4}} 關於兩個自反生成元的凱萊圖 同一個群 D 4 {\displaystyle D_{4}} ,亦可畫出不同的凱萊圖,如右圖。 b {\displaystyle b} 仍表示左右反射,而 c {\displaystyle c} 則是關於主對角線的反射,以粉紅色線表示。由於兩個反射皆自反,右邊的凱萊圖完全無向。對應的群展示是 ⟨ b , c ∣ b 2 = c 2 = e , b c b c = c b c b ⟩ . {\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .} 條目開頭的圖,是兩個生成元 a , b {\displaystyle a,b} 上的自由群 ,關於生成集合 S = { a , b , a − 1 , b − 1 } {\displaystyle S=\{a,b,a^{-1},b^{-1}\}} 的凱萊圖,而正中央的黑點,是單位元 e {\displaystyle e} 。沿著邊向右走表示右乘 a {\displaystyle a} ,而沿著邊向上走表示乘以 b {\displaystyle b} 。因為自由群沒有關係 ,它的凱萊圖中沒有環 。這個凱萊圖是證明巴拿赫-塔斯基悖论 的關鍵。 右邊有離散海森堡群 海森堡群的一部分(顏色僅為方便看清分層) { ( 1 x z 0 1 y 0 0 1 ) , x , y , z ∈ Z } {\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}} 的凱萊圖。所用的三個生成元 X , Y , Z {\displaystyle X,Y,Z} ,分別對應 ( x , y , z ) = ( 1 , 0 , 0 ) , ( 0 , 1 , 0 ) , ( 0 , 0 , 1 ) {\displaystyle (x,y,z)=(1,0,0),\ (0,1,0),\ (0,0,1)} 。其關係為 Z = X Y X − 1 Y − 1 , X Z = Z X , Y Z = Z Y {\displaystyle Z=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY} ,亦可從圖中看出。本群為非交換 無窮群。雖然是三維空間,其凱萊圖的增長 卻是 4 {\displaystyle 4} 階的。[來源請求]
群 G {\displaystyle G} 通過左乘作用 在自身上(參見凱萊定理 )。這個作用可以看作 G {\displaystyle G} 作用在它的凱萊圖上。明確而言,一個元素 h ∈ G {\displaystyle h\in G} 映射一個頂點 g ∈ V ( Γ ) {\displaystyle g\in V(\Gamma )} 到另一個頂點 h g ∈ V ( Γ ) {\displaystyle hg\in V(\Gamma )} 。凱萊圖的邊集合被這個作用所保存:邊 ( g , g s ) {\displaystyle (g,gs)} 變換成邊 ( h g , h g s ) {\displaystyle (hg,hgs)} 。任何群在自身上的左乘作用是簡單傳遞 的,特別是凱萊圖是頂點傳遞 的。事實上,反向的結論也成立,即有下列等價刻劃,稱為扎比杜西定理 (英語:Sabidussi's Theorem ):
(無標記又無着色)有向圖 Γ {\displaystyle \Gamma } 是群 G {\displaystyle G} 的某個凱萊圖,當且僅當 G {\displaystyle G} 可作為圖自同構 (就是要保存邊的集合)作用在 Γ {\displaystyle \Gamma } 上,且該作用簡單傳遞。[1]
要從一個凱萊圖 Γ = Γ ( G , S ) {\displaystyle \Gamma =\Gamma (G,S)} 找回群 G {\displaystyle G} 和生成集 S {\displaystyle S} ,先選擇一個頂點 v 1 ∈ V ( Γ ) {\displaystyle v_{1}\in V(\Gamma )} ,標上群的單位元 e {\displaystyle e} 。接著,對 Γ {\displaystyle \Gamma } 的每個頂點 v {\displaystyle v} , G {\displaystyle G} 中有唯一元素將 v 1 {\displaystyle v_{1}} 變換到 v {\displaystyle v} ,於是可以在 v {\displaystyle v} 處標記該唯一元素。最後要確定 G {\displaystyle G} 的哪個生成集 S {\displaystyle S} ,產生凱萊圖 Γ {\displaystyle \Gamma } ,而所求的 S {\displaystyle S} 就是毗連 v 1 {\displaystyle v_{1}} 的頂點標記的集合。生成集合是有限(這是凱萊圖的共同假定)當且僅當這個圖是局部有限的(就是說每個頂點僅毗連於有限多條邊)。
如果生成集合的成員 s {\displaystyle s} 是自身的逆元,即 s = s − 1 {\displaystyle s=s^{-1}} ,則它一般被表示為無向邊 。 凱萊圖 Γ ( G , S ) {\displaystyle \Gamma (G,S)} 本質上依賴於如何選擇生成集 S {\displaystyle S} 。例如,如果生成集合 S {\displaystyle S} 有 k {\displaystyle k} 個元素,則凱萊圖的每個頂點都有 k {\displaystyle k} 條有向邊 進入, k {\displaystyle k} 條有向邊外出。當生成集合 S {\displaystyle S} 為對稱集,且有 r {\displaystyle r} 個元素時,凱萊圖是 r {\displaystyle r} 度的正則圖 。 在凱萊圖中的環 (“閉合路徑”)指示 S {\displaystyle S} 的元素之間的關係 。在群的凱萊複形 此一更複雜的構造中,對應於關係的閉合路徑被用多邊形 “填充”。 如果 f : G ′ → G {\displaystyle f:G'\to G} 是滿射 群同態 并且 G ′ {\displaystyle G'} 的生成集合 S ′ {\displaystyle S'} 的元素的像是不同的,則導出圖覆疊 映射 f ¯ : Γ ( G ′ , S ′ ) → Γ ( G , S ) , {\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad } 這里的 S = f ( S ′ ) {\displaystyle S=f(S')} ,特別是,如果群 G {\displaystyle G} 有 k {\displaystyle k} 個生成元,階均不為 2 {\displaystyle 2} ,并且這些生成元和它們的逆元構成集合 S {\displaystyle S} ,則該集合生成的自由群 F ( S ) {\displaystyle F(S)} 有到 G {\displaystyle G} 的滿同態(商映射),故 Γ ( G , S ) {\displaystyle \Gamma (G,S)} 被自由群的凱萊圖覆蓋,即 2 k {\displaystyle 2k} 度的無限正則樹 。 即使集合 S {\displaystyle S} 不生成群 G {\displaystyle G} ,仍可以構造圖 Γ ( G , S ) {\displaystyle \Gamma (G,S)} 。但是,此情況下,所得的圖並不連通 。在這種情況下,這個圖的每個連通分支 對應 S {\displaystyle S} 所生成子群的一個陪集。 對于有限凱萊圖(視為無向),其頂點連通性 等于這個圖的度 的 2 / 3 {\displaystyle 2/3} 。若生成集極小(即移除任一元素及其逆元,就不再生成整個群),則其頂點連通性等於度數。[2] 至於邊連通性 ,則在任何情況下皆等於度數。[3] 群 G {\displaystyle G} 的每個乘性特徵標 χ {\displaystyle \chi } 都給出 Γ ( G , S ) {\displaystyle \Gamma (G,S)} 鄰接矩陣 的特徵向量 。若 G {\displaystyle G} 為交換群,則對應的特徵值 為 λ χ = ∑ s ∈ S χ ( s ) . {\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s).} 特別地,平凡特徵標(將所有元素映至常數 1 {\displaystyle 1} )對應的特徵值,等於 Γ ( G , S ) {\displaystyle \Gamma (G,S)} 的度數,即 S {\displaystyle S} 的元素個數。若 G {\displaystyle G} 為交換群,則恰有 | G | {\displaystyle |G|} 個特徵標,故已足以確定全部特徵值。 如果轉而把頂點作為固定子群 H {\displaystyle H} 的右陪集,就得到了一個有關的構造Schreier陪集圖 ,它是陪集枚舉 或Todd-Coxeter算法 的基礎。
研究圖的鄰接矩陣 特別是應用譜圖理論 的定理能洞察群的結構。