Xem mã nguồn của Đồ thị Cayley

{{Short description|Đồ thị sinh ra từ nhóm}}
[[Hình:Cayley graph of F2.svg|right|thumb|Đồ thị Cayley của [[nhóm tự do]] trên hai phần tử sinh ''a'' và ''b'']]
<!--{{Graph families defined by their automorphisms}}-->
Trong [[toán học]], '''đồ thị Cayley''', hay còn gọi là '''đồ thị tô màu Cayley''', '''biểu đồ Cayley''', '''biểu đồ nhóm''', hay '''nhóm màu'''<ref name = CGT>{{chú thích sách |author-link=Wilhelm Magnus |first1=Wilhelm |last1=Magnus |first2=Abraham |last2=Karrass |author3-link=Baumslag–Solitar group |first3=Donald |last3=Solitar |title=Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations |url=https://books.google.com/books?id=1LW4s1RDRHQC&pg=PR2 |year=2004 |orig-year=1966 |publisher=Courier |isbn=978-0-486-43830-6 }}</ref> là [[Đồ thị (lý thuyết đồ thị)|đồ thị]] mô tả cấu trúc trừu tượng của [[nhóm (toán học)|nhóm]]. Định nghĩa của nó được lấy từ [[định lý Cayley]] (được đặt tên theo nhà toán học [[Arthur Cayley]]), và sử dụng một [[tập sinh của nhóm|tập các phần tử sinh]] của nhóm. Nó là một trong những công cụ quan trọng trong [[lý thuyết nhóm tổ hợp]] và [[lý thuyết nhóm hình học]].

== Định nghĩa ==
Gọi <math>G</math> là [[nhóm (toán học)|nhóm]] và <math>S</math> là [[tập sinh nhóm|tập sinh]] của <math>G</math>. Đồ thị Cayley <math>\Gamma = \Gamma(G,S)</math> là [[đồ thị có hướng]] [[đồ thị tô màu cạnh|tô màu cạnh]] được xây dựng như sau:<ref name=Cayley78>{{chú thích tạp chí|first1= Arthur |last1=Cayley|journal= American Journal of Mathematics | year=1878|volume=1|issue=2|pages=174–6|title=Desiderata and suggestions: No. 2. The Theory of groups: graphical representation | url=https://babel.hathitrust.org/cgi/pt?id=uc1.$c239465;view=1up;seq=194|jstor=2369306|doi=10.2307/2369306}} In his Collected Mathematical Papers 10: 403–405.</ref>

* Mỗi phần tử <math>g</math> thuộc <math>G</math> được gán 1 đỉnh: tập đỉnh của <math>\Gamma</math> đồng nhất với <math>G.</math>
* Mỗi phần tử <math>s</math> thuộc <math>S</math> được gán màu <math>c_s</math>.
* Với mọi <math>g \in G</math> và <math>s \in S</math>, có cạnh có hướng có màu <math>c_s</math> từ đỉnh tương ứng với <math>g</math> tới đỉnh tương ứng với <math>gs</math>.

Không phải mọi tác giả đều yêu cầu rằng <math>S</math> phải sinh nhóm. Nếu <math>S</math> không phải tập sinh của nhóm <math>G</math>, thì <math>\Gamma</math> là [[liên thông (lý thuyết đồ thị)|đồ thị không liên thông]] và mỗi thành phần liên thông biểu diễn lớp kề của nhóm con sinh bởi  <math>S</math>.

Nếu phần tử <math>s</math> thuộc <math>S</math> là nghịch đảo của chính nó, tức <math>s = s^{-1},</math> thì ta có thể biểu diễn nó bằng cạnh vô hướng.

Nếu tập <math>S</math> được coi là [[tập đối xứng]] (tức là <math>S = S^{-1}</math>) và không chứa phần tử đơn vị của nhóm, thì đồ thị Cayley không tô màu của nó có thể biểu diễn bằng [[đồ thị vô hướng]].

Trong [[lý thuyết nhóm hình học]], tập <math>S</math> thường mặc định là hữu hạn, tương ứng với <math>\Gamma</math> hữu hạn địa phương.

== Các ví dụ ==
* Gọi <math>G=\Z</math> là nhóm cyclic vô hạn và tập <math>S</math> chỉ chứa 1 và nghịch đảo của nó, −1 (trong ký hiệu phép cộng); thì đồ thị Cayley của nó có đường đi vô hạn.
* Tương tự, nếu <math>G=\Z_n</math> là [[nhóm cyclic]] cấp <math>n</math> và tập <math>S</math> chỉ chứa hai phần tử là phần tử sinh <math>G</math> và nghịch đảo của nó, thì đồ thị Cayley là [[đồ thị chu trình]] <math>C_n</math>. Tổng quát hơn, đồ thị Cayley của nhóm cyclic hữu hạn cấp luôn là [[đồ thị đường tròn]].
* Đồ thị Cayley của [[tích trực tiếp của nhóm]] (cùng với [[tích Descartes]] của các tập sinh làm tập sinh) là [[tích Descartes của đồ thị|tích Descartes]] của các đồ thị Cayley tương ứng.<ref>{{citation | last = Theron | first = Daniel Peter | mr = 2636729 | page = 46 | publisher = University of Wisconsin, Madison | series = Ph.D. thesis | title = An extension of the concept of graphically regular representations | year = 1988}}.</ref>  Do đó, đồ thị Cayley của nhóm Abel <math>\Z^2</math> cùng tập các phần tử sinh <math>(\pm 1,0),(0,\pm 1)</math> là [[đồ thị lưới|lưới]] vô hạn trên mặt phẳng <math>\R^2</math>, trong khi đó, tích trực tiếp của <math>\Z_n \times \Z_m</math> cùng với các phần tử sinh tương tự có đồ thị Cayley là lưới hữu hạn kích thước <math>n\times m</math> trên [[hình xuyến]].

[[Hình:Dih 4 Cayley Graph; generators a, b.svg|220px|left|thumb|Đồ thị Cayley của nhóm nhị diện <math>D_4</math> trên hai phần tử sinh ''a'' và ''b'']]
[[Tập tin:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|Đồ thị Cayley của nhóm <math>D_4</math> trên hai phần tử sinh tự nghịch đảo]]
* Đồ thị Cayley của [[nhóm nhị diện]] <math>D_4</math> trên hai phần tử sinh <math>a</math> và <math>b</math> được biểu diễn trong ảnh bên. Các mũi tên màu đỏ biểu diễn phép hợp với <math>a</math>. Bởi <math>b</math> [[Phần tử tự nghịch đảo|tự nghịch đảo]], nên các đường màu xanh của <math>b</math> là các đường vô hướng. Do đó, đồ thị hỗn hợp giữa mũi tên và cạnh: nó có 8 đỉnh, 8 mũi tên và 4 cạnh. [[Bảng Cayley]] của nhóm <math>D_4</math> có thể dẫn xuất từ [[biểu diễn quan hệ của nhóm]] <math display="block"> \langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle. </math> Đồ thị Cayley khác của nhóm <math>D_4</math> được biểu diễn ở bên phải. Phần tử <math>b</math> vẫn là phản xạ ngang và được tô bằng màu xanh, trong khi <math>c</math> là phản xạ chéo và được tô bằng màu hồng. Bởi cả hai phản xạ này đều tự nghịch đảo nên đồ thị Cayley ở bên phải hoàn toàn vô hướng. Đồ thị này tương ứng với trình diễn sau <math display="block"> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle. </math>
* Đồ thị Cayley của [[nhóm tự do]] trên hai phần tử sinh <math>a</math> và <math>b</math> tương ứng với tập <math>S = \{a, b, a^{-1}, b^{-1}\}</math> được biểu diễn ở ngay đầu bài viết, trong đó <math>e</math> là [[phần tử đơn vị]]. Đi theo đường bên phải sẽ là phép nhân bên phải với <math>a,</math> trong khi đi theo đường phía trên sẽ là phép nhân với <math>b.</math> Bởi nhóm tự do không có [[Biểu diễn quan hệ của nhóm|quan hệ]] giữa các phần tử sinh nên đồ thị Cayley của nó không có [[chu trình (lý thuyết đồ thị)|chu trình]]. Đồ thị Cayley này là [[cây (lý thuyết nhóm)|cây]] vô hạn 4-[[đồ thị chính quy|chính quy]] và là yếu tố quan trọng trong bài chứng minh [[nghịch lý Banach–Tarski]].

[[Hình:HeisenbergCayleyGraph.png|thumb|240px|right|Một phần của đồ thị Cayley cho nhóm Heisenberg.)]]
* Đồ thị Cayley của [[nhóm Heisenberg rời rạc]]  <math display="block">\left\{ \begin{pmatrix}
 1 & x & z\\
 0 & 1 & y\\
 0 & 0 & 1\\
\end{pmatrix},\ x,y,z \in \Z\right\} </math> nằm trong ảnh phải. Các phần tử sinh trong ảnh này là ba ma trận <math>X, Y, Z</math> đưa bởi các hoán vị của 1, 0, 0 các mục <math>x, y, z</math>. Các phần tử sinh này thoả mãn quan hệ <math>Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY</math>. Nhóm này là nhóm vô hạn [[nhóm không giao hoán|không giao hoán]].
[[Tập tin:Cayley_Q8_quaternion_multiplication_graph.svg|thumb|link={{filepath:Cayley_Q8_quaternion_multiplication_graph.svg}}|Đồ thị Cayley cho nhóm <math>Q_8</math> biểu diễn các chu trình phép nhân [[quaternion]] của {{red|'''i'''}}, {{green|'''j'''}} và {{blue|'''k'''}}]]

== Đặc trưng ==
Nhóm <math>G</math> tự [[Tác động nhóm|tác động]] lên chính nó bằng phép nhân trái (xem [[định lý Cayley]]). Ta có thể xem đây là tác động của <math>G</math> trên đồ thị Cayley của nó. Nói rõ hơn, phần tử <math>h\in G</math> ánh xạ đỉnh <math>g\in V(\Gamma)</math> sang đỉnh <math>hg\in V(\Gamma).</math> Tập các cạnh và màu của đỉnh được bảo toàn bởi tác động này: cạnh <math>(g,gs)</math> được ánh xạ sang cạnh <math>(hg,hgs)</math>, cả hai đều được tô màu <math>c_s</math>. Tác động nhân trái của nhóm lên chính nó có tính [[bắc cầu đơn]], và cụ thể hơn, đồ thị Cayley có tính [[đồ thị bắc cầu đỉnh|bắc cầu đỉnh]]. Từ đây, ta có định lý gần như ngược lại như sau:

{{math theorem | name = Định lý Sabidussi | math_statement = Đồ thị có hướng (chưa tô màu và chưa dán nhãn) <math>\Gamma</math> là đồ thị Cayley của nhóm <math>G</math> khi và chỉ khi nó có tác động bắc cầu đơn của nhóm <math>G</math> bằng [[tự đẳng cấu đồ thị]] (nghĩa là bảo toàn tập các cạnh có hướng).<ref>{{chú thích tạp chí|first= Gert |last=Sabidussi|author-link=Gert 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 |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free }}</ref>}}

Để thu về nhóm <math>G</math> và tập sinh <math>S</math> từ đồ thị có hướng chưa dán nhãn <math>\Gamma,</math> chọn một đỉnh <math>v_1\in V(\Gamma)</math> và nhãn nó là phần tử đơn vị của nó. Sau đó dán nhãn mỗi phần tử <math>v</math> thuộc <math>\Gamma</math> bằng phần tử phân biệt thuộc <math>G</math> ánh xạ <math>v_1</math> sang <math>v.</math> Tập sinh <math>S</math> của <math>G</math> tạo đồ thị Cayley <math>\Gamma(G,S)</math> là tập các đỉnh đích của <math>v_1</math>.

== Các tính chất cơ bản ==

* Đồ thị <math>\Gamma(G,S)</math> phụ thuộc vào việc chọn tập sinh <math>S</math>. Lấy ví dụ, nếu tập sinh <math>S</math> có <math>k</math> phần tử thì mỗi đỉnh của đồ thị Cayley sẽ có <math>k</math> mũi tên đi vào và <math>k</math> mũi tên đi ra. Trong trường hợp tập sinh <math>S</math> đối xứng chứa <math>r</math> phần tử thì đồ thị Cayley là [[đồ thị chính quy|đồ thị chính quy có hướng]] bậc <math>r.</math>
* [[chu trình (lý thuyết đồ thị)|Chu trình]] trong đồ thị Cayley biểu diễn mối quan hệ giữa các phần tử sinh trong tập <math>S.</math> Trong xây dựng [[phức Cayley]] của nhóm, các chu trình này tương ứng với quan hệ "đổ đầy" bằng các [[đa giác]]. Nghĩa là bài toán xây đồ thị Cayley cho tập quan hệ cho trước <math>\mathcal{P}</math> tương đương với giải [[bài toán từ cho nhóm|bài toán từ]] cho <math>\mathcal{P}</math>.<ref name = CGT/>
* Nếu <math>f: G'\to G</math> là [[toàn ánh|toàn cấu nhóm]] và ảnh của các phần tử thuộc tập sinh <math>S'</math> sang <math>G'</math> phân biệt với nhau, thì nó cảm sinh ra phủ các đồ thị <math display="block"> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),</math> trong đó <math>S = f(S').</math> Cụ thể hơn, nếu nhóm <math>G</math> có <math>k</math> phần tử sinh, tất cả đều có bậc khác 2, và tập <math>S</math> chỉ chứa các phần tử sinh này cùng nghịch đảo của chúng thì đồ thị Cayley <math>\Gamma(G,S)</math> được phủ bởi [[cây (lý thuyết đồ thị)|cây]] có bậc <math>2k</math> tương ứng với [[nhóm tự do]] được sinh bởi cùng tập sinh đó.
* Đối với bất kỳ đồ thị Cayley hữu hạn và vô hướng, giá trị [[Liên thông (lý thuyết đồ thị)|liên thông đỉnh]] phải lớn hơn hoặc bằng 2/3 của [[Bậc (lý thuyết đồ thị|bậc]] của đồ thị.  Nếu tập sinh tối thiểu (tức là nếu bỏ đi bất kỳ phần tử nào trong tập hợp, và nghịch đảo của phần tử đó nếu có, thì tập đó sẽ không còn là tập sinh), thì giá trị liên thông đường sẽ bằng với bậc của đồ thị.  Giá trị liên thông cạnh trong mọi trường hợp đều bằng với bậc của đồ thị.<ref>See Theorem 3.7 of {{chú thích sách | chapter=27. Automorphism groups, isomorphism, reconstruction|title=Handbook of Combinatorics|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link= Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor2-link= Martin Grötschel |editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|first=László|last=Babai|author-link=László 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}}</ref>
* Nếu <math>\rho_{\text{reg}}(g)(x) = gx</math> là biểu diễn chính quy trái cùng dạng ma trận <math>|G|\times |G|</math> được ký hiệu là <math>[\rho_{\text{reg}}(g)]</math>, thì ma trận kề <math>\Gamma(G,S)</math> là <math display="inline">A = \sum_{s\in S} [\rho_{\text{reg}}(g)]</math>.
* Mọi [[Ký tự nhân|ký tự]] nhóm <math>\chi</math> của nhóm <math>G</math> cảm sinh vectơ riêng của [[ma trận kề]] của <math>\Gamma(G,S)</math>. Khi <math>G</math> là nhóm giao hoán, thì các [[giá trị riêng]] tương ứng là  <math display="block">\lambda_\chi=\sum_{s\in S}\chi(s),</math> nằm dưới dạng <math display="block">\sum_{s\in S} e^{2\pi ijs/|G|}</math> cho các số nguyên <math>j = 0,1,\dots,|G|-1.</math>

== Đồ thị lớp ghép Schreier ==
{{main article|Đồ thị lớp ghép Schreier}}

Nếu thay vì đó ta lấy đỉnh là lớp ghép phải của nhóm con cố định <math>H,</math> thì ta thu về được đồ thị có cấu trúc tương tự, được đặt tên là [[đồ thị lớp ghép Schreier]]. Đồ thị này là nền tảng cho [[liệt kê lớp ghép]] trong [[tiến trình Todd-Coxeter]].

== Liên hệ với lý thuyết nhóm ==
Các thông tin của nhóm có thể thu về được bằng cách nghiên cứu [[ma trận kề]] của đồ thị và áp dụng các định lý trong [[lý thuyết phổ đồ thị]]. Ngược lại, đối với các tập sinh đối xứng, lý thuyết phổ và lý thuyết biểu diễn của <math>\Gamma(G,S)</math> được gắn với nhau trực tiếp: xét <math>\rho_1,\dots,\rho_k</math> là tập các biểu diễn bất khả quy đầy đủ của <math>G,</math> và <math display="inline">\rho_i(S) = \sum_{s \in S} \rho_i(s)</math> cùng với các giá trị riêng <math>\Lambda_i(S)</math>. Khi đó tập các giá trị riêng của <math>\Gamma(G,S)</math> là <math display="inline">\bigcup_i \Lambda_i(S),</math> trong đó <math>\lambda</math> là bội của <math>\dim(\rho_i)</math> cho mỗi lần <math>\lambda</math> là giá trị riêng của <math>\rho_i(S).</math>

[[Giống (hình học)|Giống]] của nhóm là giống tối thiểu của các đồ thị Cayley của nhóm đó.<ref>{{chú thích tạp chí | last=White |first=Arthur T. |title=On the genus of a group |journal=[[Transactions of the American Mathematical Society]] |volume=173 |year=1972 |pages=203–214 |mr=0317980 |doi=10.1090/S0002-9947-1972-0317980-2|doi-access=free }}</ref>

=== Lý thuyết nhóm hình học ===

== Tính mở rộng ==

Khi <math>S = S^{-1}</math>, đồ thị Cayley <math>\Gamma(G,S)</math> là <math>|S|</math>-chính quy, nên các kỹ thuật phổ có thể được dùng được phân tích [[đồ thị giãn|các tính chất mở rộng]] của đồ thị. Lấy cụ thể như nhóm giao hoán, các giá trị riêng của đồ thị Cayley dễ tính hơn so với trường hợp không giao hoán và được xác định bởi công thức <math display="inline">\lambda_\chi = \sum_{s\in S} \chi(s)</math> trong đó giá trị riêng đứng đầu bằng với <math>|S|</math>, do đó ta có thể dùng [[Lý thuyết phổ đồ thị#bất đẳng thức Cheeger|bất đẳng thức Cheeger]] để chặn tỷ lệ mở rộng cạnh sử dụng khoảng cách phổ.

Lý thuyết biểu diễn có thể dùng để xây dựng các đồ thị giãn Cayley, dưới dạng [[tính chất Kazhdan (T)]]. Mệnh đề sau được thoả mãn:<ref>Proposition 1.12 in {{chú thích tạp chí|last=Lubotzky|first=Alexander | authorlink=Alexander Lubotzky |title=Expander graphs in pure and applied mathematics | journal=[[Bulletin of the American Mathematical Society]] |year=2012 |volume=49 |pages=113–162  |arxiv=1105.2389| doi=10.1090/S0273-0979-2011-01359-3 |doi-access=free}}</ref>

{{block indent | em = 1.6 | text = ''Nếu nhóm rời rạc <math>G</math> có tính chất Kazhdan (T), và <math>S</math> là tập sinh hữu hạn và đối xứng của <math>G</math>, thì tồn tại hằng số <math>c > 0</math> chỉ dựa trên trên <math>G, S</math> sao cho với bất kỳ thương hữu hạn <math>Q</math>của <math>G</math> đồ thị Cayley <math>Q</math> tương ứng với ảnh của <math>S</math> là đồ thị giãn <math>c</math>. ''}}

Lấy ví dụ, nhóm <math>G = \mathrm{SL}_3(\Z)</math> có tính chất (T) và được sinh bởi các [[ma trận sơ cấp]] là một trong những ví dụ cụ thể của đồ thị giãn.

== Phân loại đồ thị nguyên ==

Đồ thị nguyên là đồ thị mà các giá trị riêng của nó đều là số nguyên. Mặc dù bài toán phân loại toàn bộ các đồ thị nguyên vẫn là bài toán mở, đồ thị Cayley của một số nhóm được biết luôn là đồ thị nguyên.
Sử dụng các đặc trưng của phổ của các đồ thị Cayley, lưu ý rằng <math>\Gamma(G,S)</math> là đồ thị nguyên khi và chỉ khi các giá trị riêng của <math>\rho(S)</math> là số nguyên cho mọi biểu diễn <math>\rho</math> của <math>G</math>.

=== Nhóm đơn nguyên Cayley ===

Nhóm <math>G</math> được gọi là nhóm đơn nguyên Cayley hay còn gọi là nhóm CIS nếu đồ thị Cayley liên thông <math>\Gamma(G,S)</math> là đồ thị nguyên khi tập sinh đối xứng <math>S</math> là phần bù của một nhóm con của <math>G</math>. Một kết quả từ Ahmady, Bell, và Mohar đã chứng minh rằng tất cả các nhóm CIS đều đẳng cấu với <math>\mathbb{Z}/p\mathbb{Z}, \mathbb{Z}/p^2\mathbb{Z}</math>, hoặc <math>\mathbb{Z}_2 \times \mathbb{Z}_2</math> với <math>p</math> là số nguyên tố.<ref name="CIS">{{chú thích tạp chí|last1=Ahmady|first1=Azhvan |last2=Bell|first2=Jason|last3=Mohar|first3=Bojan|authorlink3=Bojan Mohar|title=Integral Cayley graphs and groups|journal=[[SIAM Journal on Discrete Mathematics]]|volume=28|issue=2|pages=685–701|year=2014|arxiv=1307.6155 |doi=10.1137/130925487 |s2cid=207067134}}</ref> Lưu ý rằng tập <math>S</math> phải sinh ra toàn bộ nhóm <math>G</math> để cho đồ thị Cayley có tính liên thông. (Nếu <math>S</math> không sinh <math>G</math>, đồ thị Cayley vẫn có thể nguyên, nhưng bù của <math>S</math> không nhất thiết phải là nhóm con.)

Lấy ví dụ <math>G=\mathbb{Z}/5\mathbb{Z}</math>, các tập sinh đối xứng (xê xích đẳng cấu đồ thị) là
*<math>S = \{1,4\}</math>: <math>\Gamma(G,S)</math> là chu trình <math>5</math> có các giá trị riêng <math>2, \tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}</math>
*<math>S = \{1,2,3,4\}</math>: <math>\Gamma(G,S)</math> là đồ thị <math>K_5</math> cùng với các giá trị riêng <math>4, -1,-1,-1,-1</math>
Các nhóm con duy nhất của <math>\mathbb{Z}/5\mathbb{Z}</math> là nhóm tầm thường và chính nhóm đó, và tập sinh đối xứng duy nhất của <math>S</math> mà sinh ra đồ thị nguyên là bù của nhóm tầm thường. Do đó <math>\mathbb{Z}/5\mathbb{Z}</math> là nhóm CIS.

Phân loại các nhóm CIS lợi dụng tính chất sau: các nhóm con và ảnh đồng cấu của nhóm CIS cũng là nhóm CIS.<ref name="CIS" />

=== Nhóm nguyên Cayley ===

=== Tập sinh chuẩn tắc và tập sinh Euler ===

== Lịch sử ==
Đồ thị Cayley được lần đầu nghiên cứu và sử dụng cho các nhóm hữu hạn bởi [[Arthur Cayley]] trong 1878.<ref name=Cayley78/> [[Max Dehn]] trong các bài giảng chưa xuất bản của ông cho lý thuyết nhóm từ năm 1909–10 đã giới thiệu lại đồ thị Cayley dưới tên Gruppenbild (biểu đồ nhóm), dẫn tới phát triển của lý thuyết nhóm hình học ngày nay. Ứng dụng quan trọng nhất của ông là lời giải của [[bài toán từ]] cho các [[nhóm cơ bản]] của các [[Phẳng (tô pô)|phẳng]] có giống ≥ 2<ref>{{chú thích sách|title=Papers on Group Theory and Topology|last=Dehn|first=Max|publisher=Springer-Verlag|year=2012|isbn=978-1461291077|author-link=Max Dehn|orig-year=1987}} Translated from the German and with introductions and an appendix by [[John Stillwell]], and with an appendix by [[Otto Schreier]].</ref>

== Dàn Bethe ==
{{Main article|Dàn Bethe}}

== Xem thêm ==
* [[Đồ thị bắc cầu đỉnh]]
* [[Tập sinh của nhóm]]
* [[Giả thuyết Lovász]]
<!--* [[Cube-connected cycles]]-->
* [[Lý thuyết đồ thị đại số]]
* [[Đồ thị chu trình (đại số)]]

== Tham khảo ==
{{tham khảo}}

== Liên kết ngoài ==
* [http://www.weddslist.com/groups/cayley-plat/index.html Cayley diagrams]
* {{mathworld | urlname = CayleyGraph  | title = Cayley graph }}

{{DEFAULTSORT:Cayley Graph}}
[[Thể loại:Lý thuyết nhóm]]
[[Thể loại:Nhóm hoán vị]]
[[Thể loại:Họ đồ thị]]
[[Thể loại:Lý thuyết nhóm hình học]]
[[Thể loại:Đồ thị Cayley| ]]