평면 그래프

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

평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다.

예를 들어 다음의 그래프는 모두 평면 그래프이다.

한편 아래 그래프는 평면 그래프가 아니다.

엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다.

쿠라토프스키 정리[편집]

카지미에시 쿠라토프스키의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 K_5(꼭짓점이 5개인 완전 그래프)나 K_{3,3}(각 부분의 꼭짓점이 3개씩인 완전 이분 그래프)을 세분(subdivision)으로 가지는 부분그래프가 없다는 것이다.

클라우스 바그너(독일어: Klaus Wagner)의 정리는 이와 비슷하지만 완전히 같지는 않다. 이 정리에 따르면 어떤 그래프가 평면 그래프일 필요충분조건은 그 그래프에 K_5K_{3,3}마이너로 갖지 않는다는 것이다.

성질[편집]

평면 그래프의 오일러 지표는 2이다. 즉, 꼭짓점의 수를 v, 변의 수를 e, 면의 수를 f라고 하면, 평면 그래프의 경우 다음의 식이 성립한다.

v - e + f = 2

이때 면은 변으로 닫혀진 유한한 넓이의 면뿐만이 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K3 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다.

4색정리에 의하면, 평면 그래프에서는 인접한 두 꼭짓점이 다른 색을 갖도록 4개의 색깔로 꼭짓점을 칠할 수 있다.

바깥 고리[편집]