그래프 이론

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭짓점과 7개의 변을 갖는 그래프

그래프 이론(문화어: 그라프 리론, graph理論, 영어: graph theory)은 그래프의 특성을 연구하는 조합론컴퓨터 과학의 분야이다.

주요 개념[편집]

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

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

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

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

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

분야[편집]

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

  • 대수적 그래프 이론(영어: algebraic 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년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문으로 여겨진다. 이 논문에서, 오일러는 그래프한붓그리기 존재 여부에 대한 간단한 필요충분조건을 제시하였다. 이 논문은 그래프 이론을 넘어서, 위상수학의 최초의 논문 가운데 하나이다.

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

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

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

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]