케일리 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[군론]]과 [[그래프 이론]]에서 '''케일리 그래프'''({{llang|en|Cayley graph}})는 군의 구조를 반영하는 [[그래프]]이다.

== 정의 ==
군 <math>G</math> 및 부분집합 <math>S\subset G</math>가 주어졌다고 하자. '''케일리 그래프''' <math>\Gamma(G,S)</math>는 다음과 같은 [[그래프]]이다.
*<math>G</math>의 원소를 꼭짓점으로 갖는다. 즉 <math>V(\Gamma(G,S))=G</math>.
*각각의 원소 <math>h\subset G</math>와 <math>s\subset S</math>에 대하여, <math>h</math>와 <math>sh</math>를 연결하는 변을 갖는다. 즉 <math>(g,h)\in E(\Gamma(G,S))\iff gh^{-1}\in S</math>.
<math>S</math>가 <math>G</math>의 생성집합일 때, <math>\Gamma(G,S)</math>는 연결그래프가 되고, 그렇지 않을 때 비연결 그래프가 된다. 

<math>S^{-1}=S</math> 및 <math>1\not\in S</math>라고 할 때, 케일리 그래프는 <math>|S|/2</math>색의 자연스러운 변 [[그래프 색칠|색칠]]을 갖는다. 색의 집합은 <math>S/(x\sim x^{-1}\;\forall x\in G)</math>이며, 변 <math>gh\in E(\Gamma(G,S))</math>의 색은
:<math>\{gh^{-1},hg^{-1}\}\in S/(x\sim x^{-1}\;\forall x\in G)</math>
이다. 또한, 케일리 그래프는 <math>G</math>의 자연스러운 [[군의 작용|작용]]을 가지며, 이는 [[그래프]]의 [[자기동형사상]]이다.

== 성질 ==
'''자비두시 정리'''({{llang|en|Sabidussi theorem}})에 따르면, 그래프 <math>\Gamma</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>\Gamma\cong\Gamma(G,S)</math>인 <math>S\subset G</math>가 존재한다.
* <math>\Gamma</math> 위에는 <math>G</math>의 [[군의 작용|정추이적 작용]]이 존재하며, 이 작용은 <math>\Gamma</math>의 [[그래프]] [[자기동형사상]]이다.
이는 [[오스트리아]]의 수학자 게르트 자비두시({{llang|de|Gert Sabidussi}})가 증명하였다.<ref>{{저널 인용|first= Gert |last=Sabidussi|journal=Proceedings of the American Mathematical Society|year=1958|number=5|pages=800–804|title=On a Class of Fixed-Point-Free Graphs}}</ref>

케일리 그래프 <math>\Gamma(G,S)</math>는 <math>|S|</math>-[[정규 그래프]]이다.

군 <math>G</math> 및 <math>1\not\in S=S^{-1}\subset G</math>에 대하여, 다음이 서로 [[동치]]이다.
* <math>\Gamma(G,S)</math>는 국소 유한 그래프이다. (즉, 모든 꼭짓점의 차수가 유한하다.)
* <math>S</math>는 [[유한 집합]]이다.
군 <math>G</math> 및 <math>1\not\in S=S^{-1}\subset G</math>에 대하여, 다음이 서로 [[동치]]이다.
* <math>\Gamma(G,S)</math>는 유한 그래프이다. (즉, 꼭짓점의 수가 유한하다.)
* <math>G</math>는 [[유한군]]이다.
군 <math>G</math> 및 <math>1\not\in S=S^{-1}\subset G</math>에 대하여, 다음이 서로 [[동치]]이다.
* <math>\Gamma(G,S)</math>는 연결 그래프이다.
* <math>G=\langle S\rangle</math>이다. 즉, <math>S</math>는 <math>G</math>의 생성 집합이다.
<math>\Gamma(G,S)</math>의 연결 성분의 수는 [[부분군의 지표]] <math>|G:\langle S\rangle|</math>이다.

== 예 ==
[[파일:Cayley graph of F2.svg|섬네일|오른쪽|자유군의 케일리 그래프 <math>\Gamma(\langle a,b\rangle,\{a,b,a^{-1},b^{-1}\})</math>]]
[[무한 순환군]] <math>\mathbb Z</math>의 케일리 그래프 <math>\Gamma(\mathbb Z,\{\pm1\})\cong P_\infty</math>는 무한 [[경로 그래프]]이다.

[[순환군]]의 케일리 그래프 <math>\Gamma(\mathbb Z/n,\{\pm1\})\cong C_n</math>는 [[순환 그래프]]이다.

임의의 [[곱군]] <math>G\times H</math>의 케일리 그래프는 각 성분의 케일리 그래프의 [[데카르트 곱 그래프]]이다.
:<math>\Gamma(G\times H,S_G\times S_H)\cong\Gamma(G,S_G)\square\Gamma(H,S_H)</math>

[[자유군]] <math>\langle a,b\rangle</math>의 케일리 그래프 <math>\Gamma(\langle a,b\rangle,\{a,b,a^{-1},b^{-1}\})</math>는 무한 4차 [[나무 (그래프 이론)|나무]]이다. 이 케일리 그래프는 [[바나흐-타르스키 역설]]의 증명에 등장한다.

== 역사 ==
[[아서 케일리]]가 1878년에 도입하였다.<ref>{{저널 인용|성=Cayley|이름=A.|날짜=1878|제목=Desiderata and suggestions. № 2. The theory of groups: graphical representation|url=https://archive.org/details/sim_american-journal-of-mathematics_1878_1/page/n188|저널=American Journal of Mathematics|권=1|쪽=174–176|doi=10.2307/2369306|jstor=2369306|언어=en}}</ref> [[막스 덴]]이 1909년에 이를 재발견하였으며, "군 그림"({{llang|de|Gruppenbild|그루펜빌트}}, {{llang|de|Gruppe|그루페}}(군) + {{llang|de|Bild|빌트}}(그림))이라고 이름붙였다.

== 같이 보기 ==
* [[대수적 그래프 이론]]
== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류}}
* {{매스월드|id=CayleyGraph|title=Cayley graph}}

[[분류:군론]]
[[분류:순열군]]
[[분류:그래프족]]
[[분류:기하군론]]
[[분류:대수적 그래프 이론]]
[[분류:그래프의 응용]]