3. Graph Colouring

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 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 문제를 풀면 다음과 같이 나타낼 수 있다.