일반화 페테르센 그래프

위키백과, 우리 모두의 백과사전.
(페테르센 그래프에서 넘어옴)
이동: 둘러보기, 검색

그래프 이론에서, 일반화 페테르센 그래프(一般化Petersen graph, 영어: generalized Petersen graph)는 같은 수의 꼭짓점을 갖는 정다각형과 별 모양에서 대응하는 꼭짓점들을 이어 얻는 그래프이다. 특히, 오각형과 오각 별을 이어 얻는 그래프를 페테르센 그래프(영어: Petersen graph)라고 한다.[1]

정의[편집]

3 이상의 정수 과, 의 배수가 아닌 정수 , 가 주어졌다고 하자. 또한, 만약 이 짝수라면 라고 하자.

일반화 페테르센 그래프 는 다음과 같은 그래프이다.

여기서 첨자는 으로 계산한다. 즉, 로 간주한다. 일반화 페테르센 그래프의 변 가운데, 꼴의 변을 바큇살(영어: spoke)이라고 한다.

당연히

이므로, 보통

를 가정한다.

성질[편집]

기초적 성질[편집]

페테르센 그래프 속의 완벽 부합

일반화 페테르센 그래프 개의 꼭짓점과 개의 변을 가지는 삼차 그래프이며, 완벽 부합을 갖는다. 구체적으로, 위와 같은 표기에서, 완벽 부합을 이룬다.

동형[편집]

임의의 정수 및 정수 에 대하여, 다음 두 조건이 서로 동치이다.[2]:Proposition 9[3]

예를 들어, 이다.

안둘레[편집]

일반화 페테르센 그래프 안둘레는 항상 이하이다.[4]:Theorem 2.1

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

이다. 그 속에서

는 길이 8의 순환이며,

는 길이 순환이며,

는 길이 순환이다.

또한, 다음이 성립한다.

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

이다. 그 속에서

은 길이 의 순환이다 (복부호 동순).

위 상계 가운데 적어도 하나가 포화된다. 즉, 만약 이며,

일 때, 일반화 페테르센 그래프 안둘레는 다음 표에서, 위에서부터 가장 먼저 해당하는 행에 의해 주어진다.[4]:Theorem 2.8

조건 안둘레
3
4
5
6
7
그 밖의 경우 8

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

이다. 일반화 페테르센 그래프 속의 모든 순환은 당연히 짝수 개의 바큇살 을 포함한다.

모든 일반화 페테르센 그래프는 4개의 바큇살을 갖는 길이 8의 순환

을 가지며, 바큇살 6개 이상의 순환의 길이는 항상 12 이상이다. 따라서, 2개의 바큇살 및 0개의 바큇살을 갖는 순환들만 고려하면 된다.

2개의 바큇살을 갖는 순환은 (편의상 첫 변을 로 잡으면) 항상 다음과 같은 꼴이다.

이것이 존재하기 위해서는 이어야 하며, 이 경우 순환의 길이는 이다.

  • 가 최솟값이어야 하므로, 인 경우만 고려해도 된다.
    • 인 경우: 인 경우가 최적이며, 이 경우 순환의 길이는 이다.
    • 인 경우:
      • 만약 인 경우, 이다. 따라서, 이 경우 는 최솟값을 갖지 못한다.
      • 만약 일 경우, 이 경우 0개의 바큇살을 갖는 길이 의 순환이 더 짧다.
      • 만약 일 경우, 이다.
      • 위 경우를 제외하면, 이러한 순환의 길이가 8 미만인 경우는 남는 것은 이다.

0개의 바큇살을 갖는 순환은 또는 로만 구성된다. 만으로 구성되는 유일한 순환의 길이는 이며, 만으로 구성되는 순환의 길이는 이다.

  • 후자의 길이가 7 이하가 되려면, 가능한 경우는 이다.

케일리 그래프[편집]

나우루 그래프 대칭군 케일리 그래프이다.

일반화 페테르센 그래프 에 대하여, 다음 두 조건이 서로 동치이다.[5]

예를 들어, 나우루 그래프 의 경우 이며, 이는 대칭군 케일리 그래프이다. 마찬가지로, 각기둥 그래프 는 크기 정이면체군 케일리 그래프이다. 반면, 페테르센 그래프 케일리 그래프가 아니다.

꼭짓점 색칠[편집]

일반화 페테르센 그래프는 삼차 그래프이므로, 브룩스 정리(영어: Brooks’ theorem)에 의하여 그 색칠수는 2 또는 3이다. 일반화 페테르센 그래프 에 대하여, 다음 두 조건이 서로 동치이다.

  • 이분 그래프이다. (즉, 색칠수가 2이다.)
  • 이 짝수이며, 는 홀수이다.

다시 말해, 일반화 페테르센 그래프 색칠수는 다음과 같다.

여기서 논리곱(AND), 논리합(OR)이다. 예를 들어, 페테르센 그래프 색칠수는 3이다.

변 색칠[편집]

페테르센 그래프의 변 색칠수는 4이다.[6] 페테르센 그래프는 변 색칠수가 4 이상인 가장 작은 삼차 그래프이다. 반면, 페테르센 그래프가 아닌 다른 모든 일반화 페테르센 그래프의 변 색칠수는 3이다.[7]

일반화 페테르센 그래프 는 (색들의 순열을 무시하면) 유일한 3색 변 색칠을 갖는다.

해밀턴 경로[편집]

임의의 일반화 페테르센 그래프 (, )에 대하여, 다음 두 가지 가운데 정확히 하나가 성립한다.[8]

  • (가) 해밀턴 순환을 갖는다.
  • (나) 이며, 이다.

또한, (나)의 경우, 임의의 꼭짓점을 제거하면 이는 해밀턴 순환을 갖는다. (특히, 모든 일반화 페테르센 그래프는 항상 해밀턴 경로를 갖는다.)

예를 들어, 페테르센 그래프 해밀턴 경로를 가지지만, (나)의 경우에 해당하므로 해밀턴 순환을 가지지 못한다.

교차수[편집]

각기둥 그래프인 일반화 페테르센 그래프 평면 그래프이다. 즉, 그래프 교차수가 0이다.

페테르센 그래프 그래프 교차수는 2이다. 나우루 그래프 그래프 교차수는 8이다. 특히, 이 두 그래프 둘 다 평면 그래프가 아니다.

평면 그래프가 아닌 모든 그래프는 완전 그래프 또는 완전 이분 그래프 그래프 마이너로 가지는데, 페테르센 그래프 는 이 둘 다를 그래프 마이너로 갖는다.

[편집]

일부 일반화 페테르센 그래프는 다음과 같은 특별한 이름을 갖는다.

  • 페테르센 그래프는 일반화 페테르센 그래프 이다. 이는 완전 그래프 선 그래프여 그래프와 동형이다.
  • 뒤러 그래프(영어: Dürer graph)는 일반화 페테르센 그래프 이다.
  • 일반화 페테르센 그래프 정십이면체의 꼭짓점 및 변들로 구성된 그래프와 같다.
  • 데자르그 그래프(영어: Desargues graph)는 일반화 페테르센 그래프 이다.
  • 일반화 페테르센 그래프 각형 각기둥의 꼭짓점 및 변들로 구성된 그래프와 같다.

역사[편집]

알브레히트 뒤러의 판화 《멜란콜리아 1》
데자르그의 정리에 등장하는 작도. 10개의 점 와 10개의 직선 에 각각 어떤 그래프의 꼭짓점을 대응시키고, 인접하는 점과 직선에 대응하는 두 꼭짓점 사이를 변으로 이으면, 데자르그 그래프 를 얻는다.

독일의 판화가 알브레히트 뒤러의 1514년 판화 《멜란콜리아 1》(독일어: Melancholia Ⅰ)에는 다면체가 등장하는데, 그 꼭짓점과 변으로 구성된 그래프는 뒤러 그래프이다.

1898년에 덴마크의 수학자 율리우스 페테르센이 이 그래프를 다룬 3쪽의 논문을 출판하였으며,[9]:227, Fig. 5 이로부터 명명되었다. 페테르센은 이 그래프를 다음과 같은 (잘못된) 추측에 대한 반례로 제시하였다.

연결 삼차 그래프 가운데, 임의의 변을 제거하더라도 연결 그래프로 남는 것들의 경우, 모두 변 색칠수가 3 이하이다.

“데자르그 그래프”라는 이름은 프랑스의 수학자 지라르 데자르그의 이름을 딴 것이다. 데자르그가 연구한 사영기하학의 한 정리에서 등장하는 작도에서, 각 직선과 각 점에 그래프 꼭짓점을 대응시키며, 서로 인접하는 점과 직선(에 대응하는 두 꼭짓점) 사이를 변으로 이으면, 이는 데자르그 그래프가 된다.

해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다.[10]:418, §2 콕서터는 일반화 페테르센 그래프 로 표기하였으며, 이에 특별한 이름을 부여하지 않았다.

1969년에 마크 왓킨스(영어: Mark E. Watkins)가 이 그래프 족을 “일반화 페테르센 그래프”(영어: generalized Petersen graph)라고 명명하였다.[11]

“나우루 그래프”(영어: Nauru graph)라는 이름은 데이비드 아서 엡스타인(영어: David Arthur Eppstein)이 도입하였으며, 이 그래프의 구성에 등장하는 12각 별 모양이 나우루의 국기에 등장하는 별과 흡사하기 때문에 붙여졌다.

참고 문헌[편집]

  1. Holton, D. A.; Sheehan, J. (1993). 《The Petersen graph》. Cambridge University Press. ISBN 0-521-43594-3. doi:10.2277/0521435943. 
  2. Boben, Marko; Pisanski, Tomaž; Žitni, Arjana (2005년 11월). “I-graphs and the corresponding configurations” (PDF). 《Journal of Combinatorial Designs》 (영어) 13 (6): 406–424. doi:10.1002/jcd.20054. 
  3. Steimle, Alice; Staton, William (2009년 1월 6일). “The isomorphism classes of the generalized Petersen graphs”. 《Discrete Mathematics》 (영어) 309 (1): 231–237. doi:10.1016/j.disc.2007.12.074. 
  4. Ferrero, Daniela; Hanusch, Sarah (2014). “Component connectivity of generalized Petersen graphs” (PDF). 《International Journal of Computer Mathematics》 (영어) 91 (9): 1940–1963. ISSN 0020-7160. doi:10.1080/00207160.2013.878023. 
  5. Nedela, Roman; Škoviera, Martin (1995년 1월). “Which generalized petersen graphs are Cayley graphs?”. 《Journal of Graph Theory》 (영어) 19 (1): 1–11. doi:10.1002/jgt.3190190102. 
  6. Naserasr, Reza; Škrekovski, Riste (2003년 7월 6일). “The Petersen graph is not 3-edge-colorable—a new proof”. 《Discrete Mathematics》 (영어) 268 (1–3): 325–326. doi:10.1016/S0012-365X(03)00138-9. 
  7. Castagna, Frank; Prins, Geert Caleb Ernst (1972). “Every generalized Petersen graph has a Tait coloring”. 《Pacific Journal of Mathematics》 (영어) 40 (1). ISSN 0030-8730. MR 304223. Zbl 0236.05106. doi:10.2140/pjm.1972.40.53. 
  8. Alspach, Brian R. (1983). “The classification of Hamiltonian generalized Petersen graphs”. 《Journal of Combinatorial Theory B》 (영어) 34: 293–312. MR 0714452. doi:10.1016/0095-8956(83)90042-4. 
  9. Petersen, Julius Peter Christian (1898). “Sur le théorème de Tait”. 《L’Intermédiaire des Mathématiciens》 (프랑스어) 5: 225–227. 
  10. Coxeter, Harold Scott MacDonald (1950). “Self-dual configurations and regular graphs”. 《Bulletin of the American Mathematical Society》 (영어) 56 (5): 413–455. doi:10.1090/S0002-9904-1950-09407-5. 
  11. Watkins, Mark E. (1969). “A theorem on Tait colorings with an application to the generalized Petersen graphs”. 《Journal of Combinatorial Theory》 (영어) 6: 152–164. doi:10.1016/S0021-9800(69)80116-X. 

외부 링크[편집]