페테르센 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
페테르센 그래프
페테르센 그래프의 교차수(영어: crossing number)는 2이다.

그래프 이론에서, 페테르센 그래프(영어: Petersen graph)는 꼭짓점 10개, 변 15개를 가지고 있는 그래프이다. 여러 가지 추측들의 반례로 쓰인다.

정의[편집]

일반화 페테르센 그래프(영어: generalized Petersen graph) G(n,k)는 다음과 같은 그래프이다.

V(G(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}
E(G(n,k))=\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\}

여기서 첨자는 n으로 계산한다. 즉, u_{n+i}=u_iv_{n+i}=u_i로 간주한다.

페테르센 그래프는 일반화 페테르센 그래프 G(5, 2)이다.

성질[편집]

페테르센 그래프는 평면 그래프가 아니며, 완전 그래프 K_5완전 이분 그래프 K_{3,3}마이너로 가진다.

페테르센 그래프는 K_5선 그래프여 그래프와 동형이다.

페테르센 그래프는 3가지 색으로 변을 칠할 수 없는 제일 작은 삼차 그래프이다.

페테르센 그래프는 해밀턴 경로를 가지고 있지만, 해밀턴 순환을 가지고 있지 않다.

페테르센 그래프의 교차수(영어: crossing number)는 2이다.

역사[편집]

1898년에 덴마크의 수학자 율리우스 페테르센(덴마크어: Julius Petersen)이 이 그래프를 다룬 논문을 출판하였으며,[1] 이로부터 명명되었다.

해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다.[2]

참고 문헌[편집]

  1. (프랑스어) Petersen, Julius (1898년). Sur le théorème de Tait. 《L’Intermédiaire des Mathématiciens》 5: 225–227.
  2. (영어) Coxeter, H. S. M. (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.

바깥 고리[편집]