해밀턴 경로: 두 판 사이의 차이

내용 삭제됨 내용 추가됨
잔글 210.107.196.210(토론)의 12433719판 편집을 되돌림
잔글편집 요약 없음
1번째 줄:
[[파일:Hamiltonian path.svg|thumb|[[정십이면체]]의 모든 꼭지점을 지나는 해밀턴 회로]]
'''해밍턴해밀턴 경로'''({{llang|en|Hamiltonian path}})는 어떤 그래프에서 모든 [[꼭지점]]을 단 한번만 지나는 [[경로]]를 의미한다. 또한, '''해밀턴 회로''', '''해밀턴 사이클'''(Hamiltonian cycle)은 모든 꼭지점을 단 한번만 지나는 [[회로]]를 의미한다. 이 이름은 [[아일랜드]]의 [[수학자]] [[윌리엄 로언 해밀턴]]의 이름을 따서 지어졌다.
 
어떤 그래프에서 해밀턴 경로가 존재하는지 여부를 묻는 문제는 [[NP-완전]] 문제에 속한다.
6번째 줄:
== 관련 정리 ==
 
=== 디랙의 정리 (1952) ===
[[노드]]의 수가 n개인(n>2) 그래프의 각 노드의 [[차수]]가 n/2이상이면 해밀턴 회로가 있다.
 
=== 오레의 정리 (1960) ===
15번째 줄:
* [[외판원 문제]]
* [[오일러 경로]]
 
{{토막글|수학}}
 
[[분류:그래프 이론]]
[[분류:NP-완전 문제]]