| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2000년 10월 12일 목요일 오후 06시 13분 31초 제 목(Title): Re: 6 EDGES. multi-graph(두 vertex 간을 잇는 edge를 2 이상 허용, self-loop도 허용)가 아닌 simple graph에서, 6 regular(모든 vertex의 degree가 정확히 6)인 경우엔 plannar가 아닙니다. 6 이상인 경우에도 되는지는 종이의 여백이 부족해서 증명을 중단합니다. ^^ (A4 한 장에 끄적거리다보니...) 증명 아이디어요? 1. v - e + f = 2 (잘 아시는 오일러 공식) 2. 3v = e ( Sum degre(v) = 2 e) 3. 3f <= 2e ( Sum degree(f) = 2 e) 이 식을 풀어보면 답이 없습니다. 2번 가정이 틀렸다는거죠. 일반적인 경우라면 2번 조건을 3v >= e 로 바꾸면 되겠죠. -- 박.. |