EXCELSIOR

3. Graph Colouring 본문

Graph Theory

3. Graph Colouring

Excelsior-JH 2020. 3. 22. 17:35

이번 포스팅은 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 문제를 풀면 다음과 같이 나타낼 수 있다.




'Graph Theory' 카테고리의 다른 글

3. Graph Colouring  (1) 2020.03.22
2. Representation, Sameness and Parts  (0) 2020.03.01
1. Introduction  (0) 2020.02.24
1 Comments
댓글쓰기 폼