yjlee270   4달 전

트리는 간단히 풀리는 것 같은데,

그래프에서는 어떻게 4색을 칠해야 할지 알수가 없네요.

4색 정리를 보면 n^2이라고 되어 있는데 혹 자료가 있으면 부탁드립니다.

koosaga   4달 전

0. 네 트리에서는 쉽고요. 2개의 색만으로도 칠할 수 있습니다. 

1. 모든 그래프가 4색으로 칠할 수 있는게 아니라 (4색 정리에 의해서) 평면 그래프만 4색으로 칠할 수 있습니다. 

2. 그래프를 4개의 색으로 칠하는 방법은 백트래킹으로 구할 수 있습니다.ㅍ그보다 빠른 방법은 유명한 난제 중 하나에 속합니다. (P-NP 문제) 

3. 다만 평면그래프에선 말씀하신 n^2 방법이 있나 보네요. 전 잘 모르겠습니다. 

4. .. 근데 이거 문제와 관련없는 질문인거 맞죠?

댓글을 작성하려면 로그인해야 합니다.