그래프 이론

6개의 꼭지점과 7개의 변을 가지는 그래프

그래프 이론(문화어: 그라프 리론, graph理論,영어: graph theory)은 그래프의 특성을 연구하는 수학과 컴퓨터 과학의 한 분야로, 특정 집단내 대상들 간의 관계를 그래프로 나타낸 수학적 구조이다. 여기서의 그래프는 꼭지점(영어: node 노드^[*]와 두 꼭지점을 연결하는 변(영어: edge 에지^[*])으로 구성되어 있다. 이러한 그래프 가운데 무향 그래프(영어: undirected graph)는 꼭지점들 간에 차이가 없음을 의미하며, 유향 그래프(영어: directed graph) 그래프 역시 존재한다. 그래프 이론에서의 그래프와 다른 일반 수학적인 그래프와 혼동하지 말아야 한다.

역사

그래프 이론 최초의 연구결과로는 레온하르트 오일러가 1736년에 쾨니히스베르크의 다리 문제에 관해 쓴 논문이 있다. 이 논문은 그래프 이론의 초기 논문이기도 하지만 동시에 위상학의 초기 논문으로도 알려져 있다.

1845년에 구스타프 키르히호프는 전기 회로에서 전압과 전류를 계산하는 데 쓰이는 키르히호프 회로 법칙을 발견하여 출판하였다.

1852년에 프랜시스 거스리(영어: Francis Guthrie)는 아래와 같은 질문을 하였다.

지도를 색칠할 때 인접한 국가는 다른 색으로 칠한다고 하자. 어떠한 지도라도 4개의 색으로 칠할 수 있는가?

이 문제는 사색 문제라고 알려져 있으며 그래프 이론에 관심을 불러일으킨 계기가 된다. 이 문제를 풀기 위해 많은 그래프 이론 개념이 등장하고 이론이 발전하였다. 이 문제는 100년이 지난 후인 1976년에서야 케네스 아펠과 볼프강 하켄에 의해 풀렸다.

그래프 자료 구조

컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 자료 구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다. 이론적으로 그래프는 리스트와 행렬구조중의 하나로 구별가능하다. 하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤다. 리스트 구조는 종종 sparse graphs에 적합하며 적은 메모리 공간을 요구한다. 행렬구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공한다.

리스트 자료구조(List Structures)

발생 리스트(Incidence list) - 변들은 변으로 연결된 두 꼭지점(방향이 있다면 순서가 존재함)와 가중치(weight), 다른 특정 데이터들을 포함하는 배열로 표현된다. 면으로 연결된 두 꼭지점은 서로 인접(adjacent)한 관계라고 일컫는다.

인접 리스트(Adjacency list) - 발생 리스트와 비슷하게도, 각 꼭지점이 인접한 꼭지점들의 리스트를 가진다. 따라서 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하게 되며 동시에 B의 리스트에도 A가 포함된다. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라진다.

행렬 자료구조(Matrix Structures)

발생 행렬(Incidence matrix) - 그래프는 변(edge)을 열로하고 꼭지점(vertex)을 행으로하는 행렬로 표현되며, 행렬 [꼭지점,변]은 변의 끝점에 대한 데이터를 가진다(가장 간단한 경우: 1은 연결됨을 의미, 0은 연결되지 않음을 의미). 행렬의 크기는 $|V|\cdot |E|$ (꼭지점의 수 $\times$ 변의 수)로 나타낸다.

인접 행렬(Adjacency matrix) - 인접 행렬의 크기는 $|V|\cdot |V|$ (꼭지점의 수)로 나타낸다. 만약 꼭지점x에서 꼭지점y로 변이 존재하면 행렬성분 x행 y열의 값은 1이고 그렇지 않으면 0이다. 이것은 부분그래프(subgraph), 역(reverse)그래프를 쉽게 찾게 해준다.

키르히호프 행렬(Kirchhoff matrix)-

거리 행렬(Distance matrix)-

그래프 문제들

경로 문제

• 최단 경로 문제
• 한붓그리기

참고 문헌

• 조성진; 김한두 (2013년 3월 5일). 《조합론과 그래프이론》. 경문사. ISBN 978-896105432-4. 
• 윤영진 (2002년 7월 30일). 《그래프 이론》. 교우사. ISBN 978-898172317-0. 
• 김성진; 김한두 (2013년 3월 5일). 《조합 및 그래프이론》. 경문사. ISBN 978-898172956-1. 
• Bondy, J.A.; U. S. R. Murty (2008). 《Graph Theory》. Springer. ISBN 978-1-84628-969-9. 
• Diestel, Reinhard (2010). 《Graph Theory》. Graduate Texts in Mathematics 173 4판. ISBN 978-3-642-14278-9.  CS1 관리 - 추가 문구 (링크)
• Bollobas, Bela (1998). 《Modern Graph Theory》. Graduate Texts in Mathematics 184. Springer. doi:10.1007/978-1-4612-0619-4. ISBN 978-0-387-98488-9. 
• Godsil, Chris; Gordon F. Royle (2001). 《Algebraic Graph Theory》. Graduate Texts in Mathematics 207. Springer. doi:10.1007/978-1-4613-0163-9. ISBN 978-0-387-95241-3. 
• Koh, Khee Meng; Dong Fengming, Tay Eng Guan (2007년 3월). 《Introduction to graph theory: H3 mathematics》. World Scientific. doi:10.1142/6313. ISBN 978-981-270-525-9. 
• Clark, John; Derek Allan Holton (1991년 5월). 《A first look at graph theory》. doi:10.1142/1280. ISBN 978-981-02-0490-7. 

같이 보기

• 그래프 이론 용어사전

바깥 고리

• “Graph theory”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Graph theory”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• 그래프 이론 온라인 교재
• 비탈리 페첸킨박사의 GRaph INterface 홈페이지
• Graph Theory Software