| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2003년 11월 11일 화요일 오후 01시 23분 09초 제 목(Title): Re: 정치인 문제 > 각 edge들이 서로 겹치지 않도록 평면에 그릴 수 있으면 4색 문제로 reduce > 됩니다. 전혀 다른 문제인데요? -_- 평면에 그려지는 그래프는 4색으로 칠할 수 있지만, 어떤 경우는 3색으로도 충분할 수 있습니다. 그러나 4색이 필요한지, 3색이면 충분한지도 역시 NP-Complete랍니다. -- 박.. |