해밀턴 경로: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) |
Osteologia (토론 | 기여) |
||
23번째 줄:
=== 알고리즘 ===
어떤 그래프가 자취 존재 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 경로 문제'''라고 하며, [[NP-완전]] 문제이다. 마찬가지로, 어떤 그래프가 해밀턴 그래프인지 여부를 묻는 [[결정 문제]]
[[몬테 카를로 알고리즘]]을 사용하여, <math>n</math>개의 꼭짓점을 갖는 그래프의 해밀턴 순환 문제는 <math>O(1.657^n)</math>에 풀 수 있으며, 이분 그래프의 해밀턴 순환 문제는 <math>O(1.414^n)</math>에 풀 수 있다.<ref>{{citation
| last = Björklund | first = Andreas
| arxiv = 1008.0541
| contribution = 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)
| year = 2010
| isbn = 978-1-4244-8525-3}}</ref> [[퇴각검색]] 알고리즘을 사용하여, [[삼차 그래프]]의 해밀턴 순환 문제는 <math>O(1.251^n)</math>의 시간으로 풀 수 있다.<ref>{{책 인용
| last = Iwama | first = Kazuo
| 공저자 =Takuya Nakashima
| contribution = 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
| year = 2007
| isbn = 978-3-540-73544-1}}</ref>
== 예 ==
| |||