| [ QuizWit ] in KIDS 글 쓴 이(By): birdeee (별사랑이) 날 짜 (Date): 2003년 11월 11일 화요일 오후 04시 46분 14초 제 목(Title): Re: 정치인 문제 Graph Coloring이 맞습니다. 대표적인 예가 화학 물질이 서로 반응하는 것을 같은 그릇에 담으면 안된다는 것인데 결국 같은 문제네요. 이걸 그냥 Graph Coloring 문제로 풀기에 좀 어렵다면 Graph Partitioning 문제로 바꾸어 풀 수도 있습니다. 말하자면 k 개의 Group으로의 Graph Partitioning을 Optimize 했을 때 Cost가 0이면 k 개로 coloring이 가능합니다. Cost는 Inter-group link의 weight의 합으로 놓으면 되는데 서로 안좋아하면 1, 아니면 0으로 놓으시면 됩니다. |