케일리 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

군론그래프 이론에서, 케일리 그래프(영어: Cayley graph)는 군의 구조를 반영하는 그래프이다.

정의[편집]

및 부분집합 가 주어졌다고 하고, 라고 하자. 케일리 그래프 는 다음과 같은 그래프이다.

케일리 그래프는 색의 자연스러운 변 색칠을 갖는다. 색의 집합은 이며, 변 의 색은

이다. 또한, 케일리 그래프는 의 자연스러운 작용을 가지며, 이는 그래프자기동형사상이다.

성질[편집]

자비두시 정리(영어: Sabidussi theorem)에 따르면, 그래프 에 대하여, 다음 두 조건이 서로 동치이다.

  • 가 존재한다.
  • 위에는 정추이적 작용이 존재하며, 이 작용은 그래프 자기동형사상이다.

이는 오스트리아의 수학자 게르트 자비두시(독일어: Gert Sabidussi)가 증명하였다.[1]

케일리 그래프 -정규 그래프이다.

에 대하여, 다음이 서로 동치이다.

  • 는 국소 유한 그래프이다. (즉, 모든 꼭짓점의 차수가 유한하다.)
  • 유한 집합이다.

에 대하여, 다음이 서로 동치이다.

  • 는 유한 그래프이다. (즉, 꼭짓점의 수가 유한하다.)
  • 유한군이다.

에 대하여, 다음이 서로 동치이다.

  • 는 연결 그래프이다.
  • 이다. 즉, 의 생성 집합이다.

의 연결 성분의 수는 부분군의 지표 이다.

[편집]

자유군의 케일리 그래프

무한 순환군 의 케일리 그래프 는 무한 경로 그래프이다.

순환군의 케일리 그래프 순환 그래프이다.

임의의 곱군 의 케일리 그래프는 각 성분의 케일리 그래프의 데카르트 곱 그래프이다.

자유군 의 케일리 그래프 는 무한 4차 나무이다. 이 케일리 그래프는 바나흐-타르스키 역설의 증명에 등장한다.

역사[편집]

아서 케일리가 1878년에 도입하였다.[2] 막스 덴이 1909년에 이를 재발견하였으며, "군 그림"(독일어: Gruppenbild 그루펜빌트[*], 독일어: Gruppe 그루페[*](군) + 독일어: Bild 빌트[*](그림))이라고 이름붙였다.

참고 문헌[편집]

  1. Sabidussi, Gert (1958). “On a Class of Fixed-Point-Free Graphs”. 《Proceedings of the American Mathematical Society》 (5): 800–804. 
  2. Cayley, A. (1878). “Desiderata and suggestions. № 2. The theory of groups: graphical representation”. 《American Journal of Mathematics》 (영어) 1: 174–176. JSTOR 2369306. doi:10.2307/2369306. 

외부 링크[편집]