피터슨 그래프

위키백과 ― 우리 모두의 백과사전.

피터슨 그래프를 두 개의 오각형으로 나타낸 그림
실제 크기로
피터슨 그래프를 두 개의 오각형으로 나타낸 그림

피터슨 그래프는 꼭지점 10개, 변 15개인 오른쪽 그림과 같은 그래프로, 그래프 이론의 여러 가지 문제의 반례로 쓰이거나 유용한 예로 쓰이는 중요한 그래프이다. 이 그래프의 이름은 1898년에 이 그래프를 다룬 논문을 출판한 피터슨(Julius Petersen)을 따서 지어졌다. 이 그래프는 3가지 색으로 변을 칠할 수 없는 제일 작은 큐빅 그래프이다. 한편 해밀턴 경로는 있지만 해밀턴 회로는 가지고 있지 않다.

위키미디어 공용에 이 분류에 관한 미디어 자료가 있습니다.
Petersen graph
이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해갑시다.