| [ QuizWit ] in KIDS 글 쓴 이(By): ash (물푸레나무) 날 짜 (Date): 2003년 11월 10일 월요일 오후 09시 20분 44초 제 목(Title): Re: 정치인 문제 제 생각에는... 각 정치인을 node로, 사이 나쁜 정치인의 쌍을 edge로 두었을 때, 각 edge들이 서로 겹치지 않도록 평면에 그릴 수 있으면 4색 문제로 reduce 됩니다. 각 edge들이 서로 겹치지 않도록 평면에 그릴 수 있는지 test 하는 알고리즘은 o(n^3)이라고 나오네요. planar graph로 검색해 보세요. 그래서 제 답은 1) 있다. 2) 틀렸다. 입니다. -------- O(n^3) 이라고 썼었는데, 확인해보니 o(n^3)이네요. 수정합니다. 눈이 썩었어 T_T == 불휘기픈 남간 바람에 아니 뮐쎄 곶 됴코 여름 하나니. |