그래프 이론

위키백과, 우리 모두의 백과사전.

6개의 꼭짓점과 7개의 변을 갖는 그래프

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

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

정의[편집]

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

그래프[편집]

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

주요 개념[편집]

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

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

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

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

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

분야[편집]

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

  • 대수적 그래프 이론은 그래프의 대수학적 불변량을 정의하고, 그 성질들을 연구한다.
  • 위상 그래프 이론(영어: 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세기에, 수학·물리학의 각종 분야에서 그래프의 개념이 등장하기 시작하였다.

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

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

그래프 그림[편집]

그래프 이론 데이터 구조[편집]

참고 문헌[편집]

같이 보기[편집]

각주[편집]

  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.

외부 링크[편집]