查看“︁凱萊圖”︁的源代码

[[File:F2_Cayley_Graph.png|thumb|在兩個生成元''a''和''b''上的[[自由群]]的凱萊圖]]
'''凱萊圖'''（{{lang-en|Cayley graph}}），也叫做'''凱萊著色圖'''，是將[[離散群]]的抽象結構畫出的一種[[圖 (數學)|圖]]。它的定義是[[凱萊定理]]（以[[阿瑟·凱萊]]命名）所暗含的。畫凱萊圖時，要選定群的一個[[群的生成集合|生成元集合]]（通常有限），不同選法可能得到不同的凱萊圖。凱萊圖是{{le|組合群論|Combinatorial group theory
}}與[[幾何群論]]的中心工具。

== 定義 ==

假設<math>G </math>是[[群]]，而<math>S </math>是[[群的生成集合|G的生成集]]。凱萊圖<math>\Gamma=\Gamma(G,S) </math>，是如下構造的著色的[[有向圖]]：
* <math>G </math>的每個元素<math>g </math>對應一個[[顶点 (图论)|頂點]]。換言之，圖<math>\Gamma </math>的頂點集合<math>V(\Gamma) </math>視為與<math>G </math>等同；
* <math>S </math>中每個生成元<math>s </math>，對應一種顏色<math>c_s </math>；
* 對於任何<math>g\in G, s\in S</math>，畫一條由元素<math>g </math>至<math>gs </math>的[[有向邊]]，染成<math>c_s </math>色。換言之，邊集合<math>E(\Gamma) </math>由形如<math>(g, gs) </math>的有序對構成，邊的顏色由<math>s\in S</math>確定。

在幾何群論中，集合<math>S </math>通常取為[[有限集|有限]]、對稱（即滿足<math>S=S^{-1} </math>），并且不包含這個群的單位元<math>e</math>。在這種情況下，凱萊圖是简单[[無向圖]]：它的邊沒有方向（由對稱性），并且不包含[[自環]]（因為<math>e \notin S</math>）。

== 例子 ==

* 假設<math>G = \mathbb Z</math>是無限[[循環群]]（即整數的加法群），而集合<math>S</math>由標準生成元<math>1</math>和它的逆元（用加法符號為<math>-1</math>）構成，則它的凱萊圖是{{le|道路圖|Path graph|無窮鏈}}<!--與[[道路 (圖論)]]有差異-->。
* 類似地，如果<math>G = \mathbb Z_n</math>是<math>n</math>階[[循環群]]（模<math>n</math>的加法群），而<math>S</math>仍由<math>G</math>的標準生成元<math>1</math>與逆元<math>-1</math>構成，則凱萊圖是[[循環圖|環圖]]<math>C_n</math>。
* 群的[[直積]]的凱萊圖（新生成集取為原生成集之笛卡爾積），是對應的凱萊圖的{{le|圖的笛卡爾積|Cartesian product of graphs|笛卡爾積}}。因此阿貝爾群<math>\mathbb Z^2</math>，關於四個元素<math>(\pm 1, \pm 1)</math>組成的生成集的凱萊圖，是平面<math>\mathbb R^2</math>上的無窮[[網格圖|網格]]，而帶有類似的生成集的直積<math>\mathbb Z_n \times \mathbb Z_m</math>的凱萊圖，是[[環面]]上的<math>n</math>乘<math>m</math>有限網格。
* [[二面體群]]<math>D_4</math>有[[群的展示|群展示]]：<math display=block> \langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle. </math>左圖是關於兩個生成元<math>a</math>和<math>b</math>的凱萊圖，其中紅色箭頭表示左乘元素<math>a</math>（順時針旋轉<math>90^\circ</math>）。而因為元素<math>b</math>（左右反射）[[凱萊表|自反]]，所以表示左乘元素<math>b</math>的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有<math>8</math>個頂點、<math>8</math>條[[有向邊]]、<math>4</math>條無向邊。[[File:Dih 4 Cayley Graph; generators a, b; prefix.svg|200px|left|thumb|二面體群<math>D_4</math>關於兩個生成元<math>a</math>和<math>b</math>的凱萊圖。]][[File:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|<math>D_4</math>關於兩個自反生成元的凱萊圖]]同一個群<math>D_4</math>，亦可畫出不同的凱萊圖，如右圖。<math>b</math>仍表示左右反射，而<math>c</math>則是關於主對角線的反射，以粉紅色線表示。由於兩個反射皆自反，右邊的凱萊圖完全無向。對應的群展示是<math display=block> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle. </math>
* 條目開頭的圖，是兩個生成元<math>a, b</math>上的[[自由群]]，關於生成集合<math>S = \{a, b, a^{-1}, b^{-1}\}</math>的凱萊圖，而正中央的黑點，是[[單位元]]<math>e</math>。沿著邊向右走表示右乘<math>a</math>，而沿著邊向上走表示乘以<math>b</math>。因為自由群沒有[[群的展示|關係]]，它的凱萊圖中沒有[[環 (圖論)|環]]。這個凱萊圖是證明[[巴拿赫-塔斯基悖论]]的關鍵。
*右邊有[[離散海森堡群]] [[Image:HeisenbergCayleyGraph.png|thumb|240px|right|海森堡群的一部分（顏色僅為方便看清分層）]]
<math display = block>\left\{ \begin{pmatrix}
 1 & x & z\\
 0 & 1 & y\\
 0 & 0 & 1\\
\end{pmatrix},\ x,y,z \in \Z\right\} </math>
的凱萊圖。所用的三個生成元<math>X, Y, Z</math>，分別對應<math>(x, y, z) = (1, 0, 0),\ (0, 1, 0),\ (0, 0, 1)</math>。其關係為<math>Z = XYX^{-1}Y^{-1},\ XZ = ZX,\ YZ = ZY</math>，亦可從圖中看出。本群為[[非阿貝爾群|非交換]]無窮群。雖然是三維空間，其凱萊圖的{{le|增長率 (群論)|Growth rate (group theory)|增長}}卻是<math>4</math>階的。{{Citation needed|date=September 2020}}

== 特征 ==

群<math>G</math>通過左乘[[群作用|作用]]在自身上（參見[[凱萊定理]]）。這個作用可以看作<math>G</math>作用在它的凱萊圖上。明確而言，一個元素<math>h\in G</math>映射一個頂點<math>g\in V(\Gamma)</math>到另一個頂點<math>hg\in V(\Gamma)</math>。凱萊圖的邊集合被這個作用所保存：邊<math>(g,gs)</math>變換成邊<math>(hg,hgs)</math>。任何群在自身上的左乘作用是[[群作用|簡單傳遞]]的，特別是凱萊圖是{{le|頂點傳遞圖|Vertex-transitive graph|頂點傳遞}}的。事實上，反向的結論也成立，即有下列等價刻劃，稱為'''扎比杜西定理'''<!--按[[WP:外語譯音表/德語]]暫譯-->（{{lang-en|Sabidussi's Theorem}}）：

<blockquote>
（無標記又無着色）有向圖<math>\Gamma</math>是群<math>G</math>的某個凱萊圖，當且僅當<math>G</math>可作為[[圖自同構]]（就是要保存邊的集合）作用在<math>\Gamma</math>上，且該作用簡單傳遞。<ref>{{cite journal|first= Gert |last=Sabidussi|journal=Proceedings of the American Mathematical Society |date=October 1958 |volume=9 |number=5|pages=800–4|title=On a class of fixed-point-free graphs|trans-title = 論一類無不動點的圖 |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free|language = en }}</ref>
</blockquote>

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

== 基本性質 ==

* 如果生成集合的成員<math>s</math>是自身的逆元，即<math>s=s^{-1}</math>，則它一般被表示為[[無向邊]]。
* 凱萊圖<math>\Gamma(G,S)</math>本質上依賴於如何選擇生成集<math>S</math>。例如，如果生成集合<math>S</math>有<math>k</math>個元素，則凱萊圖的每個頂點都有<math>k</math>條[[有向邊]]進入，<math>k</math>條有向邊外出。當生成集合<math>S</math>為對稱集，且有<math>r</math>個元素時，凱萊圖是<math>r</math>度的[[正則圖]]。
* 在凱萊圖中的[[路徑 (圖論)|環]]（“閉合路徑”）指示<math>S</math>的元素之間的[[群的展示|關係]]。在群的[[凱萊複形]]此一更複雜的構造中，對應於關係的閉合路徑被用[[多邊形]]“填充”。 
* 如果<math>f: G'\to G</math>是[[滿射]][[群同態]]并且<math>G'</math>的生成集合<math>S'</math>的元素的像是不同的，則導出{{le|圖覆疊|Covering graph}}映射<math display = block> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),\quad</math>這里的<math>S=f(S') </math>，特別是，如果群<math>G</math>有<math>k</math>個生成元，階均不為<math>2</math>，并且這些生成元和它們的逆元構成集合<math>S</math>，則該集合生成的[[自由群]]<math>F(S)</math>有到<math>G</math>的滿同態（商映射），故<math>\Gamma(G,S)</math>被自由群的凱萊圖覆蓋，即<math>2k</math>度的無限正則[[樹 (圖論)|樹]]。
* 即使集合<math>S</math>不生成群<math>G</math>，仍可以構造圖<math>\Gamma(G,S)</math>。但是，此情況下，所得的圖並不[[連通圖|連通]]。在這種情況下，這個圖的每個[[連通分量 (圖論)|連通分支]]對應<math>S</math>所生成子群的一個陪集。
* 對于有限凱萊圖（視為無向），其[[連通圖|頂點連通性]]等于這個圖的[[度 (圖論)|度]]的<math>2/3</math>。若生成集極小（即移除任一元素及其逆元，就不再生成整個群），則其頂點連通性等於度數。<ref>{{cite book|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago}}{{cite web |url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |title=存档副本 |accessdate=2010-08-29 |deadurl=yes |archiveurl=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archivedate=2010-06-11 }}</ref>至於[[連通圖|邊連通性]]，則在任何情況下皆等於度數。<ref>見定理3.7，{{cite book|chapter=27. Automorphism groups, isomorphism, reconstruction|trans-chapter=第27章：自同構群、同構、重構|title=Handbook of Combinatorics|trans-title=組合手冊|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link=葛立恆|editor2-first=Martin|editor2-last=Grötschel|editor3-first=László|editor3-last=Lovász|editor3-link=洛瓦茲·拉茲洛|first=László|last=Babai|publisher=Elsevier|volume=1|isbn=9780444823465|url=https://books.google.com/books?id=5Y9NCwlx63IC|year=1995|chapter-url=http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf|access-date=2021-09-29|archive-date=2021-04-22|archive-url=https://web.archive.org/web/20210422001319/https://books.google.com/books?id=5Y9NCwlx63IC}}</ref>
* 群<math>G</math>的每個{{le|乘性特徵標|Multiplicative character}}<math>\chi</math>都給出<math>\Gamma(G,S)</math>[[鄰接矩陣]]的[[特徵向量]]。若<math>G</math>為交換群，則對應的[[特徵值]]為<math>\lambda_\chi=\sum_{s\in S}\chi(s).</math>特別地，平凡特徵標（將所有元素映至常數<math>1</math>）對應的特徵值，等於<math>\Gamma(G,S)</math>的度數，即<math>S</math>的元素個數。若<math>G</math>為交換群，則恰有<math>|G|</math>個特徵標，故已足以確定全部特徵值。

== Schreier陪集圖 ==

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

== 與群論的關係 ==

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

== 參見 ==

* [[群的生成集合]]
* [[群的展示]]

== 注釋 ==
{{reflist}}

[[Category:群論]]
[[Category:置換群]]
[[Category:图]]