(새 문서: 분류:그래프 이론 '''평면그래프'''(planar graph)는 '''평면 매장'''(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 <...) |
잔글 (→쿠라토프스키 정리와 바그너 정리) |
||
| 4번째 줄: | 4번째 줄: | ||
== 쿠라토프스키 정리와 바그너 정리 == | == 쿠라토프스키 정리와 바그너 정리 == | ||
평면그래프의 필요충분조건을 가장 간단하게 설명하는 정리이다. [[쿠라토프스키 정리]]에 따르면, [[그래프 (그래프 이론)|그래프]] <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>를 [[마이너]]<!--[[마이너 (그래프 이론)|마이너]]-->로서 갖지 않는 것이다. | |||
== 오일러 다면체 정리 == | == 오일러 다면체 정리 == | ||
2017년 11월 14일 (화) 23:07 판
평면그래프(planar graph)는 평면 매장(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 [math]\displaystyle{ \mathbb R^2 }[/math]에 변끼리 겹치지 않게 그려진 그래프이며, 평면그래프는 평면 매장과 동형(isomorphic)인 그래프를 말한다. 평면에 그려졌으므로 그래프의 면을 가장 바깥에 있는 면인 무계 면/무한 면/외면(unbounded/infinite/external, outer face)과 외면이 아닌 유계 면/유한 면/내면(bounded/finite/inner face)으로 나눌 수 있다. 또한 평면과 곡면 종수(genus)가 같은 모든 곡면에 매장가능함은 평면그래프임과 동치이다.
쿠라토프스키 정리와 바그너 정리
평면그래프의 필요충분조건을 가장 간단하게 설명하는 정리이다. 쿠라토프스키 정리에 따르면, 그래프 [math]\displaystyle{ G }[/math]가 평면그래프일 필요충분조건은 [math]\displaystyle{ G }[/math]가 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]의 세분할(subdivision)과 동형(isomorphic)인 부분그래프를 갖지 않는 것이다. 즉 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]을 위상적 마이너로서 갖지 않는 것이다. 이와 비슷하게, 바그너 정리는 그래프 [math]\displaystyle{ G }[/math]가 평면그래프일 필요충분조건은 [math]\displaystyle{ G }[/math]가 [math]\displaystyle{ K_5 }[/math]나 [math]\displaystyle{ K_{3,3} }[/math]를 마이너로서 갖지 않는 것이다.