3. Graph Colouring
Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다.
Chap03 - Graph Colouring
Chap02 - Representation, Sameness, and Parts 에서는 Graph를 표현하는 방법, 두 그래프의 동일함을 의미하는 Isomorphism 그리고 Graph의 부분집합인 subgraph에 대해 살펴보았다.
이번 Chap03에서는 Graph의 vertex 에 대해 같은 색(color)이 인접하지 않도록 색을 부여하는 방법인 Graph Colouring에 대해 알아보도록 하자.
3.1 Notions and notation
먼저, Graph 에 대해 개의 컬러(color)를 부여하는 -colouring에 대한 정의는 다음과 같다.
Definition 3.1
A -colouring of an undirected graph is a function
that assign distinct values to adjacent vertices: that is, .
If has a -colouring then it is said to be -colourable.
위의 정의에서 확인할 수 있듯이, undirected graph 의 인접한 두 vertex 에 다른 색을 개 부여하는 방법을 의미한다.
위의 예시 그림을 통해 다음을 알 수 있다.
, 개의 vertex를 가진 complete graph는 -colourable 하다.
, 개와 개의 vertex로 구성된 complete bipartite graph는 -colourable 하다.
Definition 3.2
The chromatic number is the smallest number such that is -colourable.
Lemma 3.3
A graph has chromatic number if and only if it is bipartite.
위의 예시 그림을 -colourable인 최소의 정수 를 의미하는 chromatic number (정의 3.2)를 사용하여 나타내면, 과 로 표현할 수 있다.
아래의 Lemma(보조정리) 3.4 - 3.5는 수식적인 증명 없이 직관적으로 이해할 수 있다.
Lemma 3.4
If is a subgraph of and is -colourable, then so is .
Lemma 3.5
If is a subgraph of then .
만약, 가 complete graph도 아니고, cycle graph도 아니라면, chromatic number는 다음을 만족한다.
3.2 An algorithm to do colouring
위에서 살펴본 는 -colourable 한 최소의 의 개수를 의미한다.
하지만, 이런 를 구할 수 있는 최적의 알고리즘은 존재하지 않는다.
따라서, -colouring 문제는 휴리스틱(heuristic)한 방법을 사용한다.
The greedy colouring algorithm
-colouring 문제에 대한 greedy colouring algorithm에 대해 살펴보자.
greedy algorithm
graph , edge set , vertex set 그리고 adjacency lists 가 있고, 인 함수를 정의하자.
이 때, edge , 즉 인접한 두 노드에 대한 함수 는 이다.
(1) Set for .
(2) .
(3) for {
(4)
}
(5) End of loop over vertices .
위의 greedy 알고리즘을 설명하면 다음과 같다.
노드들을 1 부터 까지 번호를 매기고,
초기 1번 노드에 대해 로 설정한다.
그런 다음, 번호를 1증가 시킨 후 해당 번호의 노드에 색을 칠한다.
이 때, 인접한 노드들과는 다른 색을 실한다.
하지만, 이런 greedy algorithm은 항상 최적의 해 를 찾는것은 아니다.
만약 아래의 예시와 같이 vertex에 대한 번호를 다르게 매길경우 과 의 그래프는 서로 isomorphic 하더라도 다른 를 가지게 된다.
3.3 An application: avoiding clashes
위에서 살펴본 Graph colouring을 이용하여 스케줄링(scheduling) 문제를 풀 수 있다.
아래의 예시와 같이 멤버(member)들이 서로 겹치지 않도록 하는 위원회(commitee)의 미팅을 스케줄링 하는 방법을 graph colouring을 이용해 풀 수 있다.
위의 표에서 committee를 하나의 vertex로 설정하고, edge를 멤버가 속해있는 committee로 설정한 후에 graph colouring 문제를 풀면 다음과 같이 나타낼 수 있다.
