페테르센 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
페테르센 그래프를 두 개의 오각형으로 나타낸 그림

페테르센 그래프(Petersen graph)는 꼭지점 10개, 변 15개를 가지고 있는 그래프로, 그래프 이론의 여러 가지 문제의 반례로 쓰이거나 유용한 예로 쓰이는 중요한 그래프이다. 이 그래프의 이름은 1898년에 이 그래프를 다룬 논문을 출판한 덴마크의 수학자 페테르센(Julius Petersen)을 따서 지어졌다.

성질[편집]

페테르센 그래프의 crossing number는 2이다.

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

페테르센 그래프는 K_5라인 그래프여 그래프 관계에 있다.

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

페테르센 그래프는 해밀톤 경로를 가지고 있지만, 해밀톤 회로는 가지고 있지 않다.

페테르센 그래프의 crossing number는 2이다.

일반화된 페테르센 그래프[편집]

도널드 콕세터는 1950년 페테르센 그래프의 일반화된 그래프를 도입했다. 일반화된 페테르센 그래프 G(n,k)는 다음과 같이 정의된다.

  • 그래프의 꼭지점은 \{u_0, u_1, \cdots, u_{n-1}, v_0, v_1, \cdots, v_{n-1}\}로 구성된다.
  • 그래프의 변은 \{u_i u_{i+1}, u_i v_i, v_i v_{i+k} | i = 0, 1, \cdots, n-1\}로 구성된다.

이때 각 기호의 첨자가 n-1을 넘어가는 경우 a_{n+i} = a_i로 간주한다. 페테르센 그래프 자체는 G(5, 2)로 표기할 수 있다.