그래프 이론

그래프 이론(graph理論, 영어: graph theory, 문화어: 그라프리론)은 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프를 연구하는 수학과 컴퓨터 과학의 분야이다. 그래프는 꼭짓점과 이를 연결하는 변으로 구성된다. 두 점을 연결하는 변에 방향이 있는 그래프를 유향 그래프라 하며, 방향이 없는 무향 그래프와 구분된다. 그래프는 이산수학에서 다루는 주요 수학적 대상 중 하나이다.

정의

그래프

그래프는 꼭짓점(영어: vertex)과, 2개의 꼭짓점을 연결하는 변(영어: edge)으로 구성되어 있다. 꼭짓점은 정점 또는 노드라고도 하며, 변은 간선 또는 모서리라고도 한다. 일반적으로 꼭짓점은 점 또는 원으로, 변은 점과 점을 잇는 선으로 평면 위에 그려서 그래프를 나타낸다. 엄밀하게는 그래프를 어떤 곡면 위에 표시할 수 있는데, 이를 그래프 그리기라 한다.

일반적으로^[1] 그래프(영어: graph) $G$ 는 다음의 집합들로 구성된 순서쌍 $(V,E)$ 으로 정의된다.

꼭짓점 집합 $V$
변 집합 $E\subseteq \{\{x,y\}|x,y\in V,x\neq y\}$

엄밀하게는, 무향 단순 그래프에 대해서 위의 방식처럼 정의한다. 그래프에 추가적인 구조를 부여하면 다양한 정의의 그래프를 얻을 수 있는데, 아래는 그러한 예시이다.

그래프의 각 변에 방향을 추가한 것을 유향 그래프라 한다.
그래프가 중복되는 변을 가질 수 있도록 허용한 것을 다중 그래프라 한다.
그래프의 각 변에 ± 부호를 추가한 것을 부호형 그래프라 한다.

그래프 이론에서는 그래프의 변의 길이나 꼭짓점의 위치 등을 대상으로 다루지는 않는다. 따라서 그래프는 조합론적인 대상이다.

주요 개념

그래프의 구조

그래프는 각종 국소적인 구조를 가질 수 있으며, 그래프 이론에서는 이러한 구조들을 연구한다. 아래는 그래프가 가질 수 있는 구조의 예시이다.

그래프의 분류

그래프는 특정 구조를 가지는지 등의 여부에 따라 분류할 수 있으며, 그래프 이론에서는 이러한 개념 및 성질들 사이의 관계를 연구한다.

아래는 그래프 종류의 예시이다.

그래프의 성질

매칭과 커버

부합 또는 매칭은 서로 만나지 않는 변들의 집합이다. 보든 꼭짓점을 포함하는 부합을 완벽 부합이라 한다.

꼭짓점 덮개는 그래프의 모든 변의 최소한 한 끝점에 포함되어 있는 꼭짓점들의 집합이다. 변 덮개는 그래프의 모든 꼭짓점을 포함하는 변들의 집합이다.

아래는 부합 또는 덮개에 대한 정리이다.

그래프 색칠

그래프 이론에서는 그래프에 색을 부여하는 그래프 색칠에 대해서 연구한다. 특히 두 개의 인접한 꼭짓점이 같은 색을 갖지 않도록 색칠한 그래프나 두 개의 인접한 변이 같은 색을 갖지 않도록 색칠한 그래프에 대해 연구한다. 아래는 그래프 색칠에 대한 정리들이다.

분야

그래프 이론의 주요 분야는 다음과 같다.

대수적 그래프 이론은 그래프의 대수학적 불변량을 정의하고, 그 성질들을 연구한다.
- 그래프에는 인접 행렬 등을 사용하여, 선형대수학 및 스펙트럼 이론의 기법을 적용할 수 있다. 이러한 분야를 스펙트럼 그래프 이론(영어: spectral graph theory)이라고 한다.
- 그래프의 색칠 다항식 및 이를 일반화한 텃 다항식과 같은 다항식 불변량을 정의할 수 있다. 이러한 다항식 불변량은 매트로이드로 일반화할 수 있으며, 또한 매듭 이론의 매듭 다항식 불변량 (존스 다항식 등) 및 통계역학·양자장론과 관련이 있다.
- 일부 그래프는 대칭성을 갖는다. 이러한 대칭 그래프의 경우, 대칭군을 사용하여 군론적인 기법을 적용할 수 있다.
위상 그래프 이론(영어: topological graph theory)은 그래프의 곡면 속의 매장을 연구한다. 그래프의 가능한 매장에 따라, 그래프를 평면 그래프를 비롯한 각종 종수로 분류할 수 있다. 이러한 위상수학적 성질은 그래프의 다른 불변량과 관련이 있다. 예를 들어, 4색정리에 따르면, 평면 그래프의 색칠수는 항상 4 이하이다.
기하 그래프 이론(영어: geometric graph theory)은 폴리토프와 관련된 그래프들을 연구한다. 다면체의 꼭짓점과 변들은 그래프로 여길 수 있으며, 다면체의 기하학적 성질과 그 그래프의 성질을 연관지을 수 있다.
확률 그래프 이론(영어: probabilistic graph theory)은 각종 무작위 그래프의 성질들을 연구한다. 이러한 무작위 그래프들은 독특한 성질들을 보인다. 예를 들어, 오일러-레니 무작위 그래프의 경우, 꼭짓점 수가 무한한 극한을 취하면 그래프는 거의 확실하게 라도 그래프라는 그래프와 동형이 된다. 이 사실은 무작위 그래프의 1차 논리 언어의 모형 이론으로 해석할 수 있다. 또한, 이러한 무작위 그래프는 소셜 네트워크 서비스 및 기타 실재 네트워크의 모형으로 쓰인다.
극대 그래프 이론(영어: extremal graph theory)은 그래프의 크기에 관련된 각종 불변량들 사이의 부등식 및 이러한 부등식을 포화시키는 그래프들을 찾는다. 즉, 그래프의 대역적 성질을 국한시키면 어떤 국소적 구조가 필연적으로 발생하는지에 대하여 연구한다. 특히, 램지 이론은 그래프의 색칠과 관련하여, 필연적으로 발생하는 구조들을 다룬다.
알고리즘 그래프 이론(영어: algorithmic graph theory)은 유한 그래프의 각종 구조(해밀턴 경로, 클릭, 그래프 색칠)를 계산하는 알고리즘 및 이러한 알고리즘의 계산 복잡도를 연구한다. 그래프 관련 문제들 가운데 일부는 NP-완전 문제이며, 따라서 이들의 연구는 계산 복잡도 이론의 중요한 부분을 차지한다.
네트워크 이론은 그래프로 간주한 네트워크의 최적화 및 그래프의 중심성 등의 성질을 연구한다.
조합적 집합론(영어: combinatorial set theory)은 무한 그래프의 성질들을 연구한다. 이 경우, 그래프의 고유 성질보다는 집합론의 기법이 더 중요하다. 조합적 집합론은 모형 이론 등 논리학에 응용된다.

역사

쾨니히스베르크의 다리 문제는 그래프 이론의 시초로 여겨진다.

그래프 이론의 시초는 레온하르트 오일러가 1736년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문으로 여겨진다. 이 논문에서, 오일러는 그래프의 한붓그리기 존재 여부에 대한 간단한 필요충분조건을 제시하였다. 오일러의 다면체 정리는 오귀스탱 루이 코시^[2]와 시몽 앙투안 장 륄리에^[3]에 의해 연구되고 일반화되었으며, 위상수학의 시초를 상징한다.

19세기에, 수학·물리학의 각종 분야에서 그래프의 개념이 등장하기 시작하였다.

1845년에 구스타프 키르히호프는 전기 회로를 다루는 키르히호프 회로 법칙을 발견하여 출판하였다. 키르히호프의 회로 이론은 오늘날 네트워크 이론의 시초가 되었다.
1852년에 프랜시스 거스리(영어: Francis Guthrie)는 4색 정리를 추측하였다. 간단하게 보이는 이 문제는 오랫동안 난제로 남아, 그래프 이론에 관심을 불러일으켰다.
1857년에 윌리엄 로언 해밀턴은 해밀턴 경로의 개념을 도입하였고, 곧 해밀턴 경로의 존재 여부에 대한 문제가 제기되었다.
1878년에 아서 케일리는 군의 케일리 그래프를 정의하였다.

이러한 문제들을 풀기 위해, 율리우스 페테르센, 앨프리드 켐프(영어: Alfred Kempe, 1849~1922), 쾨니그 데네시, 조지 데이비드 버코프, 해슬러 휘트니, 윌리엄 토머스 텃 등은 그래프 이론의 기초적인 개념 및 정리들을 정립하였다. 쾨니그는 1936년에 그래프 이론에 대한 최초의 책을 출판하였다.

현재, 그래프 이론은 활발한 연구 주제로 남아 있다. 비교적 최근의 주요 연구 결과로는 케네스 아펠과 볼프강 하켄의 4색 정리의 증명 (1976년), 강한 완벽 그래프 정리의 증명 (2002년) 등이 있다.

참고 문헌

조성진; 김한두 (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. Zbl 1134.05001.
Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001. 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. Zbl 0902.05016.
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. Zbl 0968.05002.
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.

같이 보기

각주

↑ Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
↑ Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", [[:fr:Journal de l'École polytechnique|]], 9 (Cahier 16): 66–86.
↑ L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.

외부 링크

위키미디어 공용에 관련된
미디어 분류가 있습니다.

그래프 이론

“Graph theory”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Graph theory”. 《Wolfram MathWorld》 (영어). Wolfram Research.

[1] Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[2] Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", [[:fr:Journal de l'École polytechnique|]], 9 (Cahier 16): 66–86.

[3] L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.

[1]

[2]

[3]