평면그래프 편집하기

[[분류:그래프 이론]]

'''평면그래프'''(planar graph)는 '''평면 매장'''(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 <math>\mathbb R^2</math>에 변끼리 겹치지 않게 그려진 그래프이며, 평면그래프는 평면 매장과 동형(isomorphic)인 그래프를 말한다. 평면에 그려졌으므로 그래프의 면을 가장 바깥에 있는 면인 '''무계 면'''/'''무한 면'''/'''외면'''(unbounded/infinite/external, outer face)과 외면이 아닌 '''유계 면'''/'''유한 면'''/'''내면'''(bounded/finite/inner face)으로 나눌 수 있다. 또한 평면과 [[곡면 종수]](genus)가 같은 모든 곡면에 매장가능함은 평면그래프임과 동치이다.

== 쿠라토프스키 정리와 바그너 정리 ==
평면그래프의 필요충분조건을 가장 간단하게 설명하는 정리이다. [[쿠라토프스키 정리]]에 따르면, [[그래프 (그래프 이론)|그래프]] <math>G</math>가 평면그래프일 필요충분조건은 <math>G</math>가 <math>K_5</math>나 <math>K_{3,3}</math>의 세분할(subdivision)과 동형(isomorphic)인 부분그래프를 갖지 않는 것이다. 즉 <math>K_5</math>나 <math>K_{3,3}</math>을 [[위상적 마이너]]로서 갖지 않는 것이다. 이와 비슷하게, [[바그너 정리]]는 그래프 <math>G</math>가 평면그래프일 필요충분조건은 <math>G</math>가 <math>K_5</math>나 <math>K_{3,3}</math>를 [[마이너]]<!--[[마이너 (그래프 이론)|마이너]]-->로서 갖지 않는 것이다.

== 오일러 다면체 정리 ==
[[오일러 다면체 정리]](Euler's polyhedral theorem)는 [[연결 (그래프 이론)|연결]]된 평면그래프 <math>G</math>의 [[오일러 표수]] <math>\chi_E(G) = v-e+f </math>가 항상 2임을 말한다. 예를 들어, 삼각형 <math>K_3</math>의 경우엔 <math>v=3,~e=3,~f=2</math> (내면과 외면)이므로 <math>v-e+f =2</math>가 성립한다. 하지만 연결되지 않은 평면그래프에서는 당연하게도 성립하지 않는다. 다만 이때는 <math>v - e + f \ge 2</math>가 성립하게 된다. (연결되도록 변을 더 그려넣으면, <math>e</math>가 증가하여 <math>\chi_E(G) = 2</math>가 될 것이다. 따라서  <math>e</math>가 더 작다면 오일러 표수는 2 이상이 될 것이다.)

오일러 표수를 이용하면 변의 수와 꼭짓점의 수 사이의 부등식을 찾을 수 있다. 먼저, 그래프의 [[안둘레]](girth) <math>g</math>를 최소 [[순환 (그래프 이론)|순환]] 길이라고 정의하자. (없으면 무한대.) 예를 들어 [[고리 (그래프 이론)|고리]]가 있는 그래프는 안둘레가 1이고, [[단순그래프]]는 안둘레가 3 이상이다. 만약 순환이 없다면, 즉 안둘레가 무한대이면, 그 그래프는 [[나무 (그래프 이론)|나무]]이고 즉 <math>v=e+1,~f=1</math>임을 한다. 이제 안둘레가 <math>3\le g < \infty</math>라고 가정하자. 그러면 (한 면, 그 면과 인접한 변)의 순서쌍의 개수는 최대 <math>2e</math> 개이며(한 변은 최대 두 개의 면과 만난다), 최소 <math>gf</math> 개이다(한 면에는 <math>g</math> 개 이상의 인접한 변이 있다). 따라서 <math>2e \ge gf</math>이며, 오일러 다면체 정리에 의하여
:<math>\displaystyle 2=v-e+f \le v-e+\frac 2 g e = v - \frac{g-2}{g} e \implies e \le \frac g {g-2} (v-2)</math>
이 됨을 알 수 있다. 예를 들어 단순 평면그래프는 <math>e\le 3v-6</math>을 만족하며, 삼각형이 없는 단순그래프나 [[이분그래프]] 같은 경우에는 안둘레가 4 이상이므로 <math>e\le 2v - 4</math>이다.

이를 이용하면 평균 차수가 
:<math>\displaystyle \operatorname{deg}(G) = \frac 1 v \sum_{x \in V(G)} \operatorname{deg}_G(x) = \frac{2e}{v} \le \frac{2g}{g-2} \frac{v-2}v < \frac{2g}{g-2}</math>
이므로, 차수가 <math>\frac{2g}{g-2}</math>보다 작은 꼭짓점이 반드시 존재하게 된다. 이는 [[그래프 채색]] 관련 문제를 다룰 때 유용하게 사용된다.

== 동전 그래프 ==

== 쌍대 그래프와 매트로이드 ==

== 사색 정리, 오색 정리와 그래프 채색 ==

== 토마슨 정리와 리스트 채색 ==

== 평면그래프의 채색과 비영 흐름 ==

== 관련 정리와 추측 ==