그래프 색칠 문제 문서 내용 보기

{{topmenu}}
= 뜻 =
* 그래프의 꼭지점, 변, 혹은 면 등을 칠하는데, 인접한 것끼리 서로 다른 색을 칠하는 문제.
* n개의 꼭지점을 위 조건대로 칠하기 위한 최소 숫자 k (색칠수 혹은 채색수, chromatic number)를 구하는 일반적 방법
* [[NP-problem|NP]]-Hard
= 참고 =
* [http://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%83%89%EC%B9%A0_%EB%AC%B8%EC%A0%9C 위키피디아 한국], "그래프 색칠 문제"