그래프 이론

6개의 꼭짓점과 7개의 변을 갖는 그래프 **그래프 이론**(그라프리론, graph理論, graph theory)은 그래프(꼭짓점과 변들로 이루어진 조합론적 구조)의 성질을 연구하는 조합론과 컴퓨터 과학의 분야이다.
# 주요 개념

## 그래프
**그래프**는 **꼭짓점**과 꼭짓점 사이의 **변**으로 구성되어 있다. 변의 길이나 꼭짓점의 위치 따위는 중요하지 않으므로, 그래프는 조합론적인 대상이다. 그래프 이론의 연구 대상은 그래프 및 추가 구조를 갖춘 그래프이다. * 그래프의 각 변에 방향을 추가하면, 유향 그래프를 얻는다. * 그래프의 각 변에 중복수를 추가하면, 다중 그래프를 얻는다. * 그래프의 각 변에 ± 부호를 추가하면, 부호형 그래프를 얻는다. * 그래프의 각 꼭짓점에 색을 추가하면, 그래프 색칠을 얻는다. Example of simple_undirected 개의 꼭짓점과 세 개의 변으로 구성된 그래프 Example of simple undirected graph with 개의 꼭짓점과 세 개의 고리가 아닌 변, 네 개의 고리로 구성된 다중 그래프 Example of simple directed 개의 꼭짓점과 네 개의 변으로 구성된 유향 그래프. 양쪽 방향 화살표는 두 개의 변을 나타낸다.
## 그래프의 국소 구조
그래프들은 또한 각종 국소적 구조들을 갖는다. 그래프의 국소적 구조의 예로는 다음을 들 수 있다. * 경로 * 꼭짓점 덮개 * 마이너 * 변 덮개 * 부분 그래프 * 부합 * 순환 * 신장 부분 그래프 * 클릭 Graph 그 경로 BDEFDCB, HAB, HDGH. 이 가운데 HDGH만이 순환이다. 부합 4x4 grid spanning 부분 그래프
## 그래프의 종류
이러한 구조들을 가지고 그래프들을 분류할 수 있다. * 나무 그래프 * 삼차 그래프 * 완벽 그래프 * 완전 그래프 * 연결 그래프 * 이분 그래프 * 정규 그래프 * 평면 그래프
# 주요 결과
다음은 그래프 이론의 중요한 결과들이다. * 4색 정리 * 바그너 정리 * 베르주 보조정리 * 브룩스 정리 * 비징의 정리 * 램지의 정리 * 쾨니그 정리 * 텃-베르주 공식 * 홀 결혼 정리 Four Colour Map 정리에 따르면, 지도를 색칠하려면 네 가지 색으로 충분하다. Petersen Wagner 그래프는 완전 그래프 K5와 완전 이분 그래프 K3,3을 마이너로 갖는다. 바그너 정리에 따르면, 이 성질은 비평면 그래프를 특징짓는다. 정리에 따르면, 유한 이분 그래프의 최대 부합과 최소 꼭짓점 덮개의 크기는 일치한다.
# 분야
그래프 이론의 주요 분야는 다음과 같다. * **대수적 그래프 이론**은 그래프의 대수학적 불변량을 정의하고, 그 성질들을 연구한다. ** 그래프에는 인접 행렬 등을 사용하여, 선형대수학 및 스펙트럼 이론의 기법을 적용할 수 있다. 이러한 분야를 **스펙트럼 그래프 이론**(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년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문으로 여겨진다. 이 논문에서, 오일러는 그래프의 한붓그리기 존재 여부에 대한 간단한 필요충분조건을 제시하였다. 오일러의 다면체 정리는 오귀스탱 루이 코시Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", , 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.에 의해 연구되고 일반화되었으며, 위상수학의 시초를 상징한다. 19세기에, 수학·물리학의 각종 분야에서 그래프의 개념이 등장하기 시작하였다. * 1845년에 구스타프 키르히호프는 전기 회로를 다루는 키르히호프 회로 법칙을 발견하여 출판하였다. 키르히호프의 회로 이론은 오늘날 네트워크 이론의 시초가 되었다. * 1852년에 프랜시스 거스리(Francis Guthrie)는 4색 정리를 추측하였다. 간단하게 보이는 이 문제는 오랫동안 난제로 남아, 그래프 이론에 관심을 불러일으켰다. * 1857년에 윌리엄 로언 해밀턴은 해밀턴 경로의 개념을 도입하였고, 곧 해밀턴 경로의 존재 여부에 대한 문제가 제기되었다. * 1878년에 아서 케일리는 군의 케일리 그래프를 정의하였다. 이러한 문제들을 풀기 위해, 율리우스 페테르센, 앨프리드 켐프(Alfred Kempe, 1849~1922), 쾨니그 데네시, 조지 데이비드 버코프, 해슬러 휘트니, 윌리엄 토머스 텃 등은 그래프 이론의 기초적인 개념 및 정리들을 정립하였다. 쾨니그는 1936년에 그래프 이론에 대한 최초의 책을 출판하였다. 현재, 그래프 이론은 활발한 연구 주제로 남아 있다. 비교적 최근의 주요 연구 결과로는 케네스 아펠과 볼프강 하켄의 4색 정리의 증명 (1976년), 강한 완벽 그래프 정리의 증명 (2002년) 등이 있다.