그래프 이론

그래프 이론(문화어: 그라프리론, graph理論, 영어: graph theory；圖論，도론)은 수학과 컴퓨터과학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이다. 이 문맥에서 그래프는 꼭짓점(버텍스/vertex), 교점(노드/node), 점(포인트/point)으로 구성되며 이것들은 변(엣지/edge, 간선), 즉 선으로 연결된다. 그래프는 무향(무방향성)일 수 있는데 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미이며, 한편 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다. (더 자세한 정의와 이러한 유형의 그래프의 변종에 대해서는 그래프 이론 용어를 참고할 것) 그래프는 이산수학의 주요 논제 가운데 하나이다.

그래프 이론의 기초적인 정의에 대해서는 그래프 이론 용어를 참고할 것.

정의

그래프 이론의 정의는 다양하다. 아래에 그래프 및 관련 수학 구조들을 정의하는 더 기초적인 방법들 중 일부를 나열한다.

그래프

가장 일반적인 의미에서^[1] 그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 간선(변)을 의미한다. 혼동을 피하기 위해, 이러한 형태의 그래프는 정확히 방향이 없으며(무향), 단순한 그래프라고 기술할 수 있다.

주요 개념

그래프는 꼭짓점 과 2개의 꼭짓점을 연결하는 변으로 구성되어 있다. 변의 길이나 꼭짓점의 위치 따위는 중요하지 않으므로, 그래프는 조합론적인 대상이다.

그래프 이론의 연구 대상은 그래프 및 추가 구조를 갖춘 그래프이다.

그래프의 각 변에 방향을 추가하면, 유향 그래프를 얻는다.
그래프의 각 변에 중복수를 추가하면, 다중 그래프를 얻는다.
그래프의 각 변에 ± 부호를 추가하면, 부호형 그래프를 얻는다.
그래프의 각 꼭짓점에 색을 추가하면, 그래프 색칠을 얻는다.

그래프들은 또한 각종 국소적 구조들을 갖는다. 그래프의 국소적 구조의 예로는 다음을 들 수 있다.

이러한 구조들을 가지고 그래프들을 분류할 수 있다.

그래프 이론에서는 이러한 개념 및 성질들 사이의 관계를 연구한다.

분야

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

대수적 그래프 이론은 그래프의 대수학적 불변량을 정의하고, 그 성질들을 연구한다.
- 그래프에는 인접 행렬 등을 사용하여, 선형대수학 및 스펙트럼 이론의 기법을 적용할 수 있다. 이러한 분야를 스펙트럼 그래프 이론(영어: 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.

같이 보기

각주

↑ See, for instance, 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] See, for instance, 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]