반응형
평면그래프
-
알고리즘: 그래프 색칠하기(m-coloring)(Backtracking 문제)알고리즘 2020. 11. 12. 17:55
m-coloring 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 같지 않도록 m개의 다른 색으로 칠하는 방법을 찾는 문제다. 예를 들어, 이 그래프에서는 두 가지 색으로 문제를 푸는 것은 불가능하다. 세가지 색을 이용하면 6가지의 해답을 얻을 수 있다 그래프 색칠하기의 주요 응용분야는 지도 색칠하기이다. (이외에도 GSM에서 주파수 할당문제, Aircraft scheduling, final exam timetable등에 사용된다) 여기서 우리는 지도를 평면그래프(planar graph)로 나타낼 수 있는데 평면그래프란 두 개의 이음선이 서로 교차하지 않도록 그린 그래프를 말한다. 다음은 왼쪽의 지도를 평면그래프로 나타낸 것이다. (만약 v1과 v5를 연결하거나 v2와 v4를 연결한다면 평면 그래..