군
G
{\displaystyle G}
S
⊂
G
{\displaystyle S\subset G}
케일리 그래프
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
그래프 이다.
G
{\displaystyle G}
V
(
Γ
(
G
,
S
)
)
=
G
{\displaystyle V(\Gamma (G,S))=G}
각각의 원소
h
⊂
G
{\displaystyle h\subset G}
s
⊂
S
{\displaystyle s\subset S}
h
{\displaystyle h}
s
h
{\displaystyle sh}
(
g
,
h
)
∈
E
(
Γ
(
G
,
S
)
)
⟺
g
h
−
1
∈
S
{\displaystyle (g,h)\in E(\Gamma (G,S))\iff gh^{-1}\in S}
S
{\displaystyle S}
G
{\displaystyle G}
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
S
−
1
=
S
{\displaystyle S^{-1}=S}
1
∉
S
{\displaystyle 1\not \in S}
|
S
|
/
2
{\displaystyle |S|/2}
색칠 을 갖는다. 색의 집합은
S
/
(
x
∼
x
−
1
∀
x
∈
G
)
{\displaystyle S/(x\sim x^{-1}\;\forall x\in G)}
g
h
∈
E
(
Γ
(
G
,
S
)
)
{\displaystyle gh\in E(\Gamma (G,S))}
{
g
h
−
1
,
h
g
−
1
}
∈
S
/
(
x
∼
x
−
1
∀
x
∈
G
)
{\displaystyle \{gh^{-1},hg^{-1}\}\in S/(x\sim x^{-1}\;\forall x\in G)}
이다. 또한, 케일리 그래프는
G
{\displaystyle G}
작용 을 가지며, 이는 그래프 의 자기동형사상 이다.
자비두시 정리 (영어 : Sabidussi theorem )에 따르면, 그래프
Γ
{\displaystyle \Gamma }
동치 이다.
Γ
≅
Γ
(
G
,
S
)
{\displaystyle \Gamma \cong \Gamma (G,S)}
S
⊂
G
{\displaystyle S\subset G}
Γ
{\displaystyle \Gamma }
G
{\displaystyle G}
정추이적 작용 이 존재하며, 이 작용은
Γ
{\displaystyle \Gamma }
그래프 자기동형사상 이다.이는 오스트리아 의 수학자 게르트 자비두시(독일어 : Gert Sabidussi )가 증명하였다.[1]
케일리 그래프
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
|
S
|
{\displaystyle |S|}
정규 그래프 이다.
군
G
{\displaystyle G}
1
∉
S
=
S
−
1
⊂
G
{\displaystyle 1\not \in S=S^{-1}\subset G}
동치 이다.
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
S
{\displaystyle S}
유한 집합 이다.군
G
{\displaystyle G}
1
∉
S
=
S
−
1
⊂
G
{\displaystyle 1\not \in S=S^{-1}\subset G}
동치 이다.
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
G
{\displaystyle G}
유한군 이다.군
G
{\displaystyle G}
1
∉
S
=
S
−
1
⊂
G
{\displaystyle 1\not \in S=S^{-1}\subset G}
동치 이다.
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
G
=
⟨
S
⟩
{\displaystyle G=\langle S\rangle }
S
{\displaystyle S}
G
{\displaystyle G}
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
부분군의 지표
|
G
:
⟨
S
⟩
|
{\displaystyle |G:\langle S\rangle |}
자유군의 케일리 그래프
Γ
(
⟨
a
,
b
⟩
,
{
a
,
b
,
a
−
1
,
b
−
1
}
)
{\displaystyle \Gamma (\langle a,b\rangle ,\{a,b,a^{-1},b^{-1}\})}
무한 순환군
Z
{\displaystyle \mathbb {Z} }
Γ
(
Z
,
{
±
1
}
)
≅
P
∞
{\displaystyle \Gamma (\mathbb {Z} ,\{\pm 1\})\cong P_{\infty }}
경로 그래프 이다.
순환군 의 케일리 그래프
Γ
(
Z
/
n
,
{
±
1
}
)
≅
C
n
{\displaystyle \Gamma (\mathbb {Z} /n,\{\pm 1\})\cong C_{n}}
순환 그래프 이다.
임의의 곱군
G
×
H
{\displaystyle G\times H}
데카르트 곱 그래프 이다.
Γ
(
G
×
H
,
S
G
×
S
H
)
≅
Γ
(
G
,
S
G
)
◻
Γ
(
H
,
S
H
)
{\displaystyle \Gamma (G\times H,S_{G}\times S_{H})\cong \Gamma (G,S_{G})\square \Gamma (H,S_{H})}
자유군
⟨
a
,
b
⟩
{\displaystyle \langle a,b\rangle }
Γ
(
⟨
a
,
b
⟩
,
{
a
,
b
,
a
−
1
,
b
−
1
}
)
{\displaystyle \Gamma (\langle a,b\rangle ,\{a,b,a^{-1},b^{-1}\})}
나무 이다. 이 케일리 그래프는 바나흐-타르스키 역설 의 증명에 등장한다.
아서 케일리 가 1878년에 도입하였다.[2] 막스 덴 이 1909년에 이를 재발견하였으며, "군 그림"(독일어 : Gruppenbild 그루펜빌트[* ] , 독일어 : Gruppe 그루페[* ] (군) + 독일어 : Bild 빌트[* ] (그림))이라고 이름붙였다.
↑ Sabidussi, Gert (1958). “On a Class of Fixed-Point-Free Graphs”. 《Proceedings of the American Mathematical Society》 (5): 800–804. ↑ Cayley, A. (1878). “Desiderata and suggestions. № 2. The theory of groups: graphical representation”. 《American Journal of Mathematics》 (영어) 1 : 174–176. doi :10.2307/2369306 . JSTOR 2369306 .
