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