EXCELSIOR

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다. Chap03 - Graph ColouringChap02 - Representation, Sameness, and Parts 에서는 Graph를 표현하는 방법, 두 그래프의 동일함을 의미하는 Isomorphism 그리고 Graph의 부분집합인 subgraph에 대해 살펴보았다.이번 Chap03에서는 Graph의 vertex ​에 대해 같은 색(color)이 인접하지 않도록 색을 부여하는 방법인 Graph Colouring에 대해 알아보도록 하자. 3.1 Notions and notation먼저, Grap..

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다. Chap02 - Representation, Sameness and PartsChap01 - Introduction에서는 전반적인 Graph Theory와 Graph 구조 및 종류에 대해 살펴보았다. 이번 Chap02에서는 Graph를 표현하는 방법, 두 그래프의 동일함을 의미하는 Isomorphism 그리고 Graph의 부분집합인 subgraph에 대해 알아보도록 하자. 2.1 Ways to represent a graph먼저 graph를 표현하는 방법에 대해 살펴보자.graph는 여러 가지 방법으로..

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다. 1. Introduction1.1 Graph Theory그래프 이론(Graph Theory)은 1736년에 그 유명한 오일러(Euler)에 의해 시작 되었다.오일러는 Königsberg Bridge Problem을 풀기 위해 아래의 그림과 같이 육지(land)를 하나의 점(point)으로 나타내고, 다리(bridge)를 선(line)으로 추상화하여 나타냈다. 이 때 사용한 방식이 바로 그래프 이론의 시초가 된다. Königsberg Bridge Problem는 다음과 같다. 이 문제의 답을 미리 말하자..