해밀턴 경로 문서 원본 보기

{{위키데이터 속성 추적}}
'''굵은 글씨'''[[파일:Hamiltonian path.svg|섬네일|[[정십이면체]]의 모든 꼭짓점을 지나는 해밀턴 순환]]
[[파일:Натурализация гамильтоновых циклов.jpg|섬네일|8*8 [[격자 그래프|그리드 그래프]]의 세 가지 예]]
[[그래프 이론]]에서 '''해밀턴 경로'''(Hamilton經路, {{llang|en|Hamiltonian path}})는 모든 [[꼭짓점]]을 한 번씩 지나는 [[경로 (그래프 이론)|경로]]이다.

== 정의 ==
[[그래프]] <math>G</math>의 '''해밀턴 경로''' <math>p</math>는 <math>G</math>의 모든 꼭짓점을 포함하는 [[경로 (그래프 이론)|경로]]이다. (정의에 따라, 경로는 꼭짓점을 중복하여 거치지 않는 [[그래프 이론 용어|보행]]이다.) '''해밀턴 순환'''({{llang|en|Hamiltonian cycle}})은 해밀턴 경로인 [[순환 (그래프 이론)|순환]]이다.

해밀턴 순환을 갖는 그래프를 '''해밀턴 그래프'''({{llang|en|Hamiltonian graph}})라고 한다. 해밀턴 경로를 갖는 그래프를 '''자취 존재 그래프'''({{llang|en|traceable graph}})라고 한다.

== 성질 ==
유한 그래프 <math>G</math>의 '''폐포'''({{llang|en|closure}}) <math>\operatorname{cl}(G)</math>는 다음 성질들을 만족시키는 가장 작은 그래프이다.
* <math>V(\operatorname{cl}(G))=V(G)</math>
* <math>E(\operatorname{cl}(G))\supset E(G)</math>
* 임의의 <math>u,v\in V(\operatorname{cl}(G))</math>에 대하여, <math>u</math>와 <math>v</math>가 같은 연결 성분에 속하지만 <math>uv\not\in E(\operatorname{cl}(G))</math>라면 <math>\deg u+\deg v<n</math>
이러한 그래프는 유일함을 보일 수 있다.

'''본디-흐바탈 정리'''({{llang|en|Bondy–Chvátal theorem}})에 따르면, 유한 그래프 <math>G</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 해밀턴 그래프이다.
* <math>G</math>의 폐포는 해밀턴 그래프이다.
특히, 크기가 3 이상인 [[완전 그래프]]는 해밀턴 그래프이므로, 폐포가 완전 그래프인 그래프는 해밀턴 그래프이다. 즉, 다음과 같은 [[따름정리]]를 얻을 수 있다. 모든 유한 그래프 <math>G</math>에 대하여, 만약 <math>|V(G)|\ge3</math>라면 다음이 성립한다.
* ('''디랙의 정리''' {{llang|en|Dirac’s theorem}}) 만약 임의의 v에 대해 <math>\deg v\ge|V(G)|/2</math>라면 <math>G</math>는 해밀턴 그래프이다.
* ('''오레의 정리''' {{llang|en|Ore’s theorem}}) 만약 모든 인접하지 않은 꼭짓점 <math>u,v\in V(G)</math>에 대하여 <math>\deg u+\deg v\ge|V(G)|</math>라면, <math>G</math>는 해밀턴 그래프이다.
디랙의 정리는 디랙({{llang|en|G. A. Dirac}})이 1952년에 증명하였다. 오레의 정리는 [[외위스테인 오레]]가 1960년에 증명하였다.

=== 알고리즘 ===
어떤 그래프가 자취 존재 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 경로 문제'''라고 하며, [[NP-완전]] 문제이다. 마찬가지로, 어떤 그래프가 해밀턴 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 순환 문제'''라고 하며, 역시 [[NP-완전]] 문제이다. [[유향 그래프]]에 대한 마찬가지 [[결정 문제]] 역시 [[NP-완전]] 문제이다.

[[몬테카를로 방법]]을 사용하여, <math>n</math>개의 꼭짓점을 갖는 그래프의 해밀턴 순환 문제는 <math>O(1.657^n)</math>에 풀 수 있으며, 이분 그래프의 해밀턴 순환 문제는 <math>O(1.414^n)</math>에 풀 수 있다.<ref>{{서적 인용
 | last = Björklund | first = Andreas
 | arxiv = 1008.0541
 | 장 = Determinant sums for undirected Hamiltonicity
 | doi = 10.1109/FOCS.2010.24
 | pages = 173–182
 | title = Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)
 | 날짜 = 2010
 | isbn = 978-1-4244-8525-3|언어=en}}</ref> [[퇴각검색]] 알고리즘을 사용하여, [[삼차 그래프]]의 해밀턴 순환 문제는 <math>O(1.251^n)</math>의 시간으로 풀 수 있다.<ref>{{서적 인용
 | last = Iwama | first = Kazuo
 | 공저자 =Takuya Nakashima
 | 장 = An improved exact algorithm for cubic graph TSP
 | doi = 10.1007/978-3-540-73545-8_13
 | pages = 108–117
 | series = Lecture Notes in Computer Science
 | title = Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007)
 | volume = 4598
 | 날짜 = 2007
 | isbn = 978-3-540-73544-1|언어=en}}</ref>

== 예 ==
[[파일:Knight's graph.svg|섬네일|오른쪽|기사 그래프. [[기사의 여행]] 문제는 기사 그래프의 해밀턴 경로 또는 해밀턴 순환을 찾는 문제이다.]]
[[파일:Turk-knights-tour.svg|섬네일|오른쪽|기사 그래프 위의 해밀턴 순환]]
[[기사의 여행]] 문제는 64개의 꼭짓점을 갖는 '''기사 그래프'''({{llang|en|knight’s graph}})에서 해밀턴 경로와 해밀턴 순환을 찾는 문제이다. 이 그래프는 8×8 [[체스판]]에서 [[나이트 (체스)|나이트]]가 움직일 수 있는 방향들을 변으로 한다.

=== 해밀턴 그래프의 예 ===
다음과 같은 그래프들은 해밀턴 그래프이다.
* 크기가 3 이상인 [[완전 그래프]]
* 크기가 3 이상인 [[순환 그래프]]
* [[정다면체]]의 그래프
다음과 같은 그래프들은 해밀턴 그래프가 아니다.
* 비연결 그래프
* [[나무 (그래프 이론)|트리]](Tree) 그래프
다음과 같은 그래프는 자취 존재 그래프이지만 해밀턴 그래프가 아니다.
* 2개 이상의 꼭짓점을 갖는 [[경로 그래프]]

== 역사 ==
[[윌리엄 로언 해밀턴]]이 1857년에 [[정십이면체]]의 그래프 위의 해밀턴 순환을 찾는 문제를 제안하였다. 해밀턴은 이 문제를 아이코시언 게임({{llang|en|icosian game}})이라고 불렀다.

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

== 외부 링크 ==
{{위키공용분류}}
* {{eom|title=Graph circuit}}
* {{매스월드|id=HamiltonianCycle|title=Hamiltonian cycle}}
* {{매스월드|id=HamiltonianPath|title=Hamiltonian path}}
* {{매스월드|id=HamiltonianGraph|title=Hamiltonian graph}}
* {{매스월드|id=OresTheorem|title=Ore's theorem}}
* {{매스월드|id=DiracsTheorem|title=Dirac's theorem}}
* {{매스월드|id=PosasTheorem|title=Pósa's theorem}}
* {{매스월드|id=ChvatalsTheorem|title=Chvátal's theorem}}

== 같이 보기 ==
* [[외판원 문제]]
* [[오일러 경로]]

[[분류:해밀턴 경로| ]]
[[분류:그래프 이론의 계산 문제]]
[[분류:NP-완전 문제]]
[[분류:윌리엄 로언 해밀턴]]