평면 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
'''평면 그래프'''({{lang|en|planar graph}})는 평면 상에 [[그래프]]를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 [[그래프]]를 의미한다.

예를 들어 다음의 그래프는 모두 평면 그래프이다.
<gallery caption="평면 그래프의 예">
파일:Butterfly graph.svg
파일:Complete graph K4.svg|이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다.
파일:CGK4PLN.svg|앞의 그래프와 같은 그래프이다.
</gallery>

한편 아래 그래프는 평면 그래프가 아니다.
<gallery caption="평면 그래프가 아닌 그래프의 예">
파일:Complete graph K5.svg|꼭짓점이 5개인 [[완전 그래프]](<math>K_5</math>)
파일:Complete bipartite graph K3,3.svg|꼭짓점이 3개씩인 [[완전 이분 그래프]](<math>K_{3,3}</math>)
파일:Petersen graph.svg|[[페테르센 그래프]]
</gallery>

엄밀하게 정의하면, 평면 그래프는 평면에 [[w:graph embedding|그래프 임베딩]]이 가능한 그래프를 의미한다.

== 쿠라토프스키 정리 ==
[[카지미에시 쿠라토프스키]]의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 [[필요충분조건]]은 그 그래프에는 <math>K_5</math>(꼭짓점이 5개인 [[완전 그래프]]) 또는 <math>K_{3,3}</math>을 [[마이너 (그래프 이론)|마이너]]로 갖지 않는다는 것이다.

== 성질 ==
평면 그래프의 [[오일러 지표]]는 2이다. 즉, 꼭짓점의 수를 <math>v</math>, 변의 수를 <math>e</math>, 면의 수를 <math>f</math>라고 하면, 평면 그래프의 경우 다음의 식이 성립한다.
:<math>v - e + f = 2</math>
이때 면은 변으로 닫힌 유한한 넓이의 면뿐만이 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K<sub>3</sub> 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다.

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

== 외부 링크 ==
* {{eom|title=Graph, planar}}
* {{매스월드|id=PlanarGraph|title=Planar graph}}
* {{매스월드|id=NonplanarGraph|title=Nonplanar graph}}
* {{매스월드|id=PlanarConnectedGraph|title=Planar connected graph}}
* {{매스월드|id=KuratowskiReductionTheorem|title=Kuratowski reduction theorem}}

{{토막글|수학}}

[[분류:평면 그래프| ]]
[[분류:그래프족]]