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

내용 삭제됨 내용 추가됨
편집 요약 없음
25번째 줄:
어떤 그래프가 자취 존재 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 경로 문제'''라고 하며, [[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