그래프 이론 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:6n-graf.svg|섬네일|right|250px|6개의 꼭짓점과 7개의 변을 갖는 그래프]]
'''그래프 이론'''(graph理論, {{llang|en|graph theory}}, {{문화어|그라프리론}})은 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 [[그래프]]를 연구하는 [[수학]]과 [[컴퓨터 과학]]의 분야이다. 그래프는 [[꼭짓점]]과 이를 연결하는 [[그래프 이론 용어|변]]으로 구성된다. 두 점을 연결하는 변에 방향이 있는 그래프를 [[유향 그래프]]라 하며, 방향이 없는 무향 그래프와 구분된다. 그래프는 [[이산수학]]에서 다루는 주요 수학적 대상 중 하나이다.

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

일반적으로<ref>Iyanaga and Kawada, '''69 J''', p.&nbsp;234 or Biggs, p.&nbsp;4.</ref> '''그래프'''({{llang|en|graph}}) <math>G</math>는 다음의 [[집합]]들로 구성된 [[순서쌍]] <math>(V,E)</math>으로 정의된다.
* 꼭짓점 집합 <math>V</math>
* 변 집합 <math>E\subseteq\{\{x,y\}|x,y\in V,x\neq y\}</math>

엄밀하게는, 무향 단순 그래프에 대해서 위의 방식처럼 정의한다. 그래프에 추가적인 구조를 부여하면 다양한 정의의 그래프를 얻을 수 있는데, 아래는 그러한 예시이다.
* [[그래프]]의 각 변에 [[방향 (다양체)|방향]]을 추가한 것을 '''[[유향 그래프]]'''라 한다.
* [[그래프]]가 중복되는 변을 가질 수 있도록 허용한 것을 '''[[다중 그래프]]'''라 한다.
* [[그래프]]의 각 변에 ± 부호를 추가한 것을 '''[[부호형 그래프]]'''라 한다.

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

== 주요 개념 ==
{{참고|그래프 이론 용어}}
=== 그래프의 구조 ===
그래프는 각종 국소적인 구조를 가질 수 있으며, 그래프 이론에서는 이러한 구조들을 연구한다. 아래는 그래프가 가질 수 있는 구조의 예시이다.
* [[경로 (그래프 이론)|경로]]
* [[순환 (그래프 이론)|순환]]
* [[부분 그래프]]
* [[신장 부분 그래프]]
* [[연결 그래프]]
* [[마이너 (그래프 이론)|마이너]]
* [[클릭 (그래프 이론)|클릭]]
* [[부합 (그래프 이론)|부합]]

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

아래는 그래프 종류의 예시이다.
* [[완전 그래프]]
* [[정규 그래프]]
* [[연결 그래프]]
* [[트리 (그래프 이론)|트리]]
* [[이분 그래프]]
* [[평면 그래프]]
* [[순환 그래프]]
* [[완벽 그래프]]

=== 그래프의 성질 ===

==== 매칭과 커버 ====
[[부합 (그래프 이론)|'''부합''']] 또는 '''매칭'''은 서로 만나지 않는 변들의 집합이다. 보든 꼭짓점을 포함하는 부합을 '''완벽 부합'''이라 한다.

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

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

* [[홀 결혼 정리]]
* [[쾨니그의 정리]]
* [[부합 (그래프 이론)#성질#베르주 보조정리|베르주 보조정리]]
* [[부합 (그래프 이론)#성질#텃-베르주 공식|텃-베르주 공식]]

==== 그래프 색칠 ====
그래프 이론에서는 그래프에 색을 부여하는 '''[[그래프 색칠]]'''에 대해서 연구한다. 특히 두 개의 인접한 꼭짓점이 같은 색을 갖지 않도록 색칠한 그래프나 두 개의 인접한 변이 같은 색을 갖지 않도록 색칠한 그래프에 대해 연구한다. 아래는 그래프 색칠에 대한 정리들이다.
* [[4색 정리]]
* [[램지의 정리]]
* [[비징의 정리]]
* [[브룩스의 정리]]

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

== 역사 ==
[[파일:Konigsberg bridges.png|섬네일|right|[[쾨니히스베르크의 다리 문제]]는 그래프 이론의 시초로 여겨진다.]]
그래프 이론의 시초는 [[레온하르트 오일러]]가 1736년에 쓴 [[쾨니히스베르크의 다리 문제]]에 대한 논문으로 여겨진다. 이 논문에서, 오일러는 [[그래프]]의 [[한붓그리기]] 존재 여부에 대한 간단한 [[필요충분조건]]을 제시하였다. [[오일러의 다면체 정리]]는 [[오귀스탱 루이 코시]]<ref>Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", [[:fr:Journal de l'École polytechnique|]], 9 (Cahier 16): 66–86.</ref>와 [[시몽 앙투안 장 륄리에]]<ref>L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.</ref>에 의해 연구되고 일반화되었으며, [[위상수학]]의 시초를 상징한다.

19세기에, 수학·물리학의 각종 분야에서 [[그래프]]의 개념이 등장하기 시작하였다.
* 1845년에 [[구스타프 키르히호프]]는 [[전기 회로]]를 다루는 [[키르히호프 회로 법칙]]을 발견하여 출판하였다. 키르히호프의 회로 이론은 오늘날 [[네트워크 이론]]의 시초가 되었다.
* 1852년에 [[프랜시스 거스리]]({{llang|en|Francis Guthrie}})는 [[4색 정리]]를 추측하였다. 간단하게 보이는 이 문제는 오랫동안 난제로 남아, 그래프 이론에 관심을 불러일으켰다.
* 1857년에 [[윌리엄 로언 해밀턴]]은 [[해밀턴 경로]]의 개념을 도입하였고, 곧 해밀턴 경로의 존재 여부에 대한 문제가 제기되었다.
* 1878년에 [[아서 케일리]]는 [[군 (수학)|군]]의 [[케일리 그래프]]를 정의하였다.
이러한 문제들을 풀기 위해, [[율리우스 페테르센]], [[앨프리드 켐프]]({{llang|en|Alfred Kempe}}, 1849~1922), [[쾨니그 데네시]], [[조지 데이비드 버코프]], [[해슬러 휘트니]], [[윌리엄 토머스 텃]] 등은 그래프 이론의 기초적인 개념 및 정리들을 정립하였다. 쾨니그는 1936년에 그래프 이론에 대한 최초의 책을 출판하였다.

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

== 참고 문헌 ==
* {{서적 인용|제목=조합론과 그래프이론|저자=조성진|공저자=김한두|날짜=2013-03-05|출판사=경문사|isbn=978-896105432-4|언어=ko}}
* {{서적 인용|제목=그래프 이론|저자=윤영진|날짜=2002-07-30|출판사=교우사|isbn=978-898172317-0|언어=ko}}
* {{서적 인용|제목=조합 및 그래프이론|저자=김성진|공저자=김한두|날짜=2013-03-05|출판사=경문사|isbn=978-898172956-1 |언어=ko}}
* {{서적 인용|last=Bondy|first=J.A.|공저자=U. S. R. Murty|title=Graph theory|publisher=Springer|날짜=2008|isbn=978-1-84628-969-9|url=http://www.springer.com/978-1-84628-969-9|zbl=1134.05001|언어=en}}
* {{서적 인용|제목=Graph theory|총서=Graduate Texts in Mathematics|권=173|성=Diestel|이름=Reinhard|판=4판|날짜=2010|isbn= 978-3-642-14278-9|url=http://diestel-graph-theory.com/|zbl=1204.05001|언어=en}}
* {{서적 인용|제목=Modern graph theory|총서=Graduate Texts in Mathematics|권=184|성=Bollobas|이름= Bela|출판사=Springer|doi=10.1007/978-1-4612-0619-4|날짜=1998|isbn=978-0-387-98488-9|zbl=0902.05016|언어=en}}
* {{서적 인용|제목=Algebraic graph theory|총서=Graduate Texts in Mathematics|권=207|성=Godsil|이름=Chris|공저자=Gordon F. Royle|출판사=Springer|doi=10.1007/978-1-4613-0163-9|날짜=2001|isbn=978-0-387-95241-3|zbl=0968.05002|언어=en}}
* {{서적 인용|제목=Introduction to graph theory: H3 mathematics|출판사=World Scientific|성=Koh|이름=Khee Meng|공저자=Dong Fengming, Tay Eng Guan|isbn= 978-981-270-525-9|날짜=2007-03|doi=10.1142/6313|언어=en}}
* {{서적 인용|제목=A first look at graph theory|이름=John|성=Clark|공저자=Derek Allan Holton |isbn=978-981-02-0490-7|날짜=1991-05 |doi=10.1142/1280|언어=en}}

== 같이 보기 ==
* [[그래프 (자료 구조)]]
* [[그래프 이론 용어]]
* [[매트로이드]]

== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류}}
* {{eom|title=Graph theory}}
* {{매스월드|id=GraphTheory|title=Graph theory}}

{{컴퓨터 과학}}
{{수학 분야}}
{{전거 통제}}

[[분류:그래프 이론| ]]