해밀턴 경로: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 편집 요약 없음 |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
1번째 줄:
[[파일:Hamiltonian path.svg|thumb|[[정십이면체]]의 모든 꼭지점을 지나는 해밀턴 회로]]
[[그래프 이론]]에서, '''해밀턴 경로'''({{llang|en|Hamiltonian path}})는
== 정의 ==
어떤 그래프에서 해밀턴 경로가 존재하는지 여부를 묻는 문제는 [[NP-완전]] 문제이다.▼
[[그래프]] <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>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>의 폐포는 해밀턴 그래프이다.
특히, [[완전 그래프]]는 해밀턴 경로이므로, 폐포가 완전 그래프인 그래프는 해밀턴 그래프이다. 즉, 다음과 같은 [[따름정리]]를 얻을 수 있다. 모든 유한 그래프 <math>G</math>에 대하여, 만약 <math>|V(G)|>2</math>라면 다음이 성립한다.
* ('''디랙의 정리''' {{llang|en|Dirac’s theorem}}) 만약 <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 x+\deg y\ge|V(G)|</math>라면, 이는 해밀턴 그래프이다.
디랙의 정리는 디랙({{llang|en|G. A. Dirac}})이 1952년에 증명하였다. 오레의 정리는 외위스테인 오레({{llang|no|Øystein Ore}})가 1960년에 증명하였다.
=== 알고리즘 ===
▲어떤 그래프에서 해밀턴 경로가 존재하는지 여부를 묻는 문제는 [[NP-완전]] 문제이다.
== 바깥 고리 ==
* {{eom|title=Graph circuit}}
* {{매스월드|id=HamiltonianCycle|title=Hamiltonian cycle}}
줄 17 ⟶ 32:
* [[외판원 문제]]
* [[오일러 경로]]
[[분류:그래프 이론]]
| |||