평면 그래프

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

평면 그래프(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개의 색깔로 꼭지점을 칠할 수 있다.

바깥 고리[편집]