suhgyuho   10달 전

정점이 n개일 때 색깔 수가 log n 개 정도 필요하다는 것은 이해가 됬는데 

왜 4개의 색깔로 칠해도 항상 답을 구할 수 있는지 이해가 안갑니다. (실제로 4개의 색깔로 칠해도 맞음)

왜 그럴까요?

kdh9949   10달 전

트리는 평면 그래프의 일종이죠. (평면 위의 점들을 이어서 나타낼 수 있으니까) 평면 그래프에서 최대 채색 수가 4라는 것은 "4색정리"라는 유명한 정리로, 이미 증명되었습니다.

https://ko.wikipedia.org/wiki/%ED%8F%89%EB%A9%B4_%...

https://ko.wikipedia.org/wiki/4%EC%83%89%EC%A0%95%...

https://en.wikipedia.org/wiki/Four_color_theorem

kdh9949   10달 전

최대 채색수라고 하니 말이 좀 이상한데 4가지 색만 써서 이웃한 정점끼리 모두 색이 다르도록 칠할 수 있다는 뜻입니다.

suhgyuho   10달 전

5개의 색을 사용했을 때 더 이득인 상황이 발생할 수도 있지 않나요?

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