그래프 색칠 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
꼭지점 6개인 그래프를 빨강, 녹색, 파랑의 세 가지 색으로 꼭지점을 칠하였다. 이 경우 두 개의 색으로는 불가능하다.

그래프 색칠 문제그래프의 꼭지점이나 변과 같은 부분에 각각 색을 칠하는 문제로, 이때 색을 칠하는 방법에 여러가지 제약이 가해진다. 예를 들어, 그래프의 꼭지점에 색을 칠하면서 인접한 두 꼭지점에는 다른 색을 할당하는 문제가 될 수 있다.

일반적으로는 그래프의 꼭지점에 색을 할당하는 문제를 주로 다루며, 변에 색을 할당하는 문제의 경우 라인 그래프의 꼭지점 색칠 문제로 바꿀 수 있다. 평면 그래프의 경우 면에 색을 칠하는 문제를 생각할 수 있는데, 이 또한 듀얼 그래프의 꼭지점 색칠 문제로 변환이 가능하다.

그래프를 색칠하는 문제는 많은 분야에 응용이 되고 있다. 예를 들어 컴파일러에서 프로세서 레지스터를 할당하는 문제, 무선 기지국 사이에서 간섭을 없애기 위한 주파수 할당 문제 등에 이용된다.

색칠수[편집]

그래프의 색칠수(채색수, chromatic number)는 그 그래프를 색칠하는 데에 필요한 최소한의 수를 의미한다. 즉, 그래프 G의 색칠수가 k일 경우 k-1개 이하의 색으로는 그 그래프를 칠할 수 없지만 k개로는 칠할 수 있다. 보통 그래프 G의 색칠수를 \chi(G)로 표기한다.

예를 들어, n개 꼭지점을 가진 완전 그래프의 색칠수는 n이다.

특정 그래프가 k개 색으로 색칠될 수 있는가를 푸는 결정 문제리처드 카프1972년에 보인 21개의 NP-완전 문제 중의 하나이다.

색칠수의 몇가지 성질들[편집]

  • \chi(G)=1 : 그래프 G의 변은 루프밖에 없다.
  • \chi(G)\ge 3 : 그래프 G가 홀수 길이의 회로를 가진다(또는, G이분 그래프가 아니다).
  • \chi(G)\ge\omega(G).
  • \chi(G)\le\Delta(G)+1.
  • G완전 그래프가 아니거나 홀수 길이의 , \chi(G)\le\Delta(G) (브룩의 정리)
  • G가 평면 그래프인 경우 \chi(G)\le 4 (사색정리)
  • G가 평면 그래프이면서, 변 3개로 구성된 회로가 없는 경우 \chi(G)\le 3 (Grötzsch의 정리)