| [ QuizWit ] in KIDS 글 쓴 이(By): constell (호이호이~!) 날 짜 (Date): 1999년 11월 15일 월요일 오후 12시 07분 46초 제 목(Title): Re: 4색 문제 입체(2차원 문제에서라면 '면')를 graph의 vertex에, 두 입체가 닿아 있는지 관계를 graph의 edge에 대응시킬 수 있겠죠? 입체의 수를 n이라고 하면.. Complete graph에 대응되는 3차원 구조에 대해서는 n개의 색이 필요합니다.(즉 최악의 경우가 됨) 따라서 모든 n에 대해서 complete graph에 대응되는 3차원 구조가 있음을 보일 수 있다면, 3차원에서는 컬러링 문제가 아주 trivial하게 되어 버리는 거죠. 증명은 어떻게 해야 할지 잘 모르겠지만..(커멘트 부탁드립니다) 일단 n개의 점들을 적당히 3차원 위에(아니면 뭐 구 위에..) 분포시킵니다. 그리고 일단 edge를 다 긋고.. edge가 교차되면 살짝 옆으로 옮겨서(^^) 교차되지 않게 하고.. 각 edge의 반쪽씩을 그쪽에 연결된 vertex의 색으로 칠하고.. 그 다음에 그 '굵기가 0인' edge들을 띵띵하게 불려서 구를 꽉 채워 버리면 complete하게 연결된 구조가 나오겠죠. 당연한 이야기지만, 2차원 평면에서는 n>=5에 대해서는 complete graph를 만들 수가 없습니다. K_5는 planar graph가 아니니까요. 그래서 2차원에서는 이게 nontrivial한 문제가 되는 거겠죠. 말하고 보니까.. 지도를 그릴 수 있는지 여부와 planar graph인지 여부는 equivalent하네요.. 그렇죠? |