평면 그래프
위키백과 ― 우리 모두의 백과사전.
평면 그래프(planar graph)란 평면 상에 꼭지점과 변을 그리되 두 변이 만나는 것은 꼭지점 상에서만 가능하도록 그릴 수 있는 그래프를 뜻한다.
예를 들어 아래 두 그래프는 평면 그래프이다.
두 번째 그래프는 비록 위 그림 상에서는 변과 변이 교차하고 있지만 다른 방식으로 그림을 그리면 교차하지 않게 할 수 있기 때문에 평면 그래프이다.
한편 아래 그래프는 평면 그래프가 아니다.
[편집] 성질
평면 그래프에서 꼭지점의 수를 v, 변의 수를 e, 면의 수를 f라고 하면 다음의 식이 성립한다.
- v − e + f = 2
이때 면은 변으로 닫혀진 유한한 넓이의 면뿐만이 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭지점 세개가 서로 연결된 K3 그래프에서 면의 수는 2가 된다.
사색정리에 의하면 평면 그래프에서는 인접한 두 꼭지점이 다른 색을 갖도록 4개의 색깔로 꼭지점을 칠할 수 있다.
| 이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |

