그래프 컬러링개요 그래프 컬러링(graph coloring) 문제는 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것이다. 이때 에지의 가중치는 사용하지 않는다. 컬러링의 주요 종류는 다음과 같다. 정점 컬러링: 가장 기본적인 형태의 그래프 컬러링. 인접한 정점들은 다른 색깔을 가져야 한다는 규칙을 따름.에지 컬러링: 각 에지를 색칠하는 데 중점을 두며, 어떤 두 에지도 같은 색깔을 가질 수 없음. 이 규칙은 에지가 공유하는 정점에도 적용됨.착색수(chromatic number): 그래프를 적절히 색칠하는 데 필요한 최소 색깔 수 (NP-완전 문제) 그래프 컬러링은 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 그래프로 모델링한 후 컬러..
