문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 그래프(이산수학) (문단 편집) === 평면성 === 그래프의 모든 변이 평면상에서 서로 교차하지 않는 위상동형 그래프를 그릴 수 있을 때, 평면성을 가진다고 한다. 해당 그래프 [math(G)]가 어떤 그래프냐에 따라서 평면성을 판정하는 방법이 달라진다. * [math(G)]가 연결 단순 그래프이고, 그래프의 차수[* 해당 그래프의 모든 닫힌 도형의 변의 수를 합한 것. 평면 그래프라면 변의 수의 2배가 된다. 이는 평면그래프는 구면상에서 정의되기 때문으로, '''그래프 외부 역시''' 도형으로 취급하기 때문.]가 [math(d\left(G\right)\geq 3)]일 때 [math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow v\geq 2+\frac{e}{3})] * [math(G)]가 연결 이분 단순 그래프이고, 그래프의 차수가 [math(d\left(G\right)\geq 3)]일 때 [math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow v\geq 2+\frac{e}{2})] * [math(G)]가 연결 단순 그래프라면 [math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow \forall e_i \in E, d\left(e_i\right)\leq 5)] 또한 쿠라토프스키 정리(Kuratowski's Theorem)에 의해서, 평면 그래프는 [math(K_5)]와 [math(K_{3,3})]의 부분분할[* 주어진 그래프의 선 위에 임의로 점을 찍은 것을 생각할 수도 있는데, 이런 그래프를 주어진 그래프의 부분분할, 혹은 세분이라고 표현한다.]을 포함하는 그래프를 내포하지 않는다는 것이 알려져 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기