평면그래프

CrMT (토론 | 기여)님의 2017년 11월 13일 (월) 19:06 판 (새 문서: 분류:그래프 이론 '''평면그래프'''(planar graph)는 '''평면 매장'''(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 <...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)


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

쿠라토프스키 정리와 바그너 정리

오일러 다면체 정리

동전 그래프

쌍대 그래프와 매트로이드

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

토마슨 정리와 리스트 채색

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

관련 정리와 추측