이산수학 그래프 채색문제

이산수학 그래프3: 그래프 채색(coloring)

그래프의 채색(coloring)

• 인접하고 있는 정점들을 서로 다른 색을 갖도록 하면서 그래프의 모든 정점에 색을 당

• 색상수

  • 그래프 채색에 필요한 최소한의 색의 수
  • x(G)로 표시한다 (ex. 4개 필요한 경우 x(G)=4)
    

• 완전 그래프에서의 색상수

  • x(k5) =5 (정점이 5개인 완전그래프)
  • x(kn)=n

• 이분 그래프에서의 색상수

  • x(k(3,3)) =2

• Simple Coloring Algorithm
  - 모든 정점들의 순서를 정한뒤, 그래프 채색의 조건을 만족하는 색상중에서 가장 낮은 번호의 색장을 선택하여 정점에 배정한다
  - 문제점: 그래프에 색상을 정하는 순서에 따라 답이 달라짐
  

• Greedy Algorithm

  • 결정을 할 때마다 최종 결과에 관계없이 그 순간에서 최선의 선택을 한다.
  • 하지만 최종의 결과 또한 최적이라는 보장이 없음