평면 그래프
평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다.
예를 들어 다음의 그래프는 모두 평면 그래프이다.
- 평면 그래프의 예
한편 아래 그래프는 평면 그래프가 아니다.
엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다.
쿠라토프스키 정리[편집]
카지미에시 쿠라토프스키의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 (꼭짓점이 5개인 완전 그래프) 또는 을 마이너로 갖지 않는다는 것이다.
성질[편집]
평면 그래프의 오일러 지표는 2이다. 즉, 꼭짓점의 수를 , 변의 수를 , 면의 수를 라고 하면, 평면 그래프의 경우 다음의 식이 성립한다.
이때 면은 변으로 닫힌 유한한 넓이의 면뿐만이 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K3 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다.
4색정리에 의하면, 평면 그래프에서는 인접한 두 꼭짓점이 다른 색을 갖도록 4개의 색깔로 꼭짓점을 칠할 수 있다.
외부 링크[편집]
- “Graph, planar”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Planar graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Nonplanar graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Planar connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Kuratowski reduction theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
![]() |
이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |