평면 그래프

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

평면 그래프(planar graph)란 평면 상에 꼭지점과 변을 그리되 두 변이 만나는 것은 꼭지점 상에서만 가능하도록 그릴 수 있는 그래프를 뜻한다.

예를 들어 아래 두 그래프는 평면 그래프이다.

두 번째 그래프는 비록 위 그림 상에서는 변과 변이 교차하고 있지만 다른 방식으로 그림을 그리면 교차하지 않게 할 수 있기 때문에 평면 그래프이다.

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

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

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.