평면 그래프 편집하기

'''평면 그래프'''(Planar Graph)는 간선이 교차하지 않고 평면(2차원 공간) 상에 그릴 수 있는 그래프를 의미한다.  그래프 이론에서 평면 그래프는 위상 기하학 및 전기 회로 설계, 네트워크 분석 등 다양한 분야에서 활용된다.
==정의==
*평면 그래프 G는 평면 위에서 간선이 교차하지 않도록 그릴 수 있는 그래프이다.
*평면 그래프가 아닌 그래프는 '''비평면 그래프(Non-Planar Graph)'''라고 한다.
==평면 그래프의 성질==
평면 그래프는 다음과 같은 성질을 만족한다.
*'''오일러 공식(Euler’s Formula)'''
**연결된 평면 그래프 G = (V, E, F)에 대해 다음 관계가 성립한다.
**V - E + F = 2
**여기서 V는 정점(Vertex)의 수, E는 간선(Edge)의 수, F는 면(Face)의 수를 의미한다.

*'''평면 그래프의 간선 수 제한'''
**간선이 많은 그래프라도 평면 그래프가 되려면 다음 조건을 만족해야 한다.
**임의의 단순 평면 그래프에 대해
***E ≤ 3V - 6 (V ≥ 3일 때)
**삼각형 그래프(각 면이 3개의 변으로 구성됨)에 대해
***E = 3V - 6
==대표적인 평면 그래프 예시==
*'''완전 그래프 K<sub>4</sub>'''
**4개의 정점이 모든 간선으로 연결된 완전 그래프는 평면 그래프이다.

*'''큐브 그래프'''
**정육면체의 모서리를 정점과 간선으로 나타낸 그래프이며 평면 그래프이다.
==비평면 그래프==
다음 그래프들은 평면 그래프가 될 수 없다.
*'''완전 그래프 K<sub>5</sub>'''
**5개의 정점이 모두 연결된 그래프 K<sub>5</sub>는 어떠한 방식으로도 평면에 교차 없이 그릴 수 없다.

*'''완전 이분 그래프 K<sub>3,3</sub>'''
**정점 집합이 두 그룹으로 나뉘고, 한 그룹의 모든 정점이 다른 그룹의 모든 정점과 연결된 그래프.
**어떠한 방식으로도 평면에서 간선이 교차하지 않도록 그릴 수 없다.
==쿠라토프스키 정리 (Kuratowski’s Theorem)==
*그래프가 평면 그래프가 아니려면 K<sub>5</sub> 또는 K<sub>3,3</sub>을 부분 그래프로 포함해야 한다.
*이는 평면 그래프 판별에 활용된다.
==평면 그래프의 응용==
*'''PCB 회로 설계'''
**전자기기에서 배선이 교차하지 않도록 설계하는 데 사용된다.

*'''지도 색칠 문제'''
**4색 정리(The Four Color Theorem)를 활용하여 지도를 최소한의 색으로 구분할 때 사용된다.

*'''네트워크 설계'''
**도로망, 철도망 등의 네트워크 최적화에 사용된다.
==같이 보기==
*[[그래프 이론]]
*[[완전 그래프]]
*[[네트워크 이론]]
*[[4색 정리]]
==참고 문헌==
*Diestel, R. (2017). ''Graph Theory''. Springer.
[[분류:자료 구조]]