해밀턴 경로: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 편집 요약 없음 |
Osteologia (토론 | 기여) |
||
25번째 줄:
어떤 그래프가 자취 존재 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 경로 문제'''라고 하며, [[NP-완전]] 문제이다. 마찬가지로, 어떤 그래프가 해밀턴 그래프인지 여부를 묻는 [[결정 문제]]는 '''해밀턴 순환 문제'''라고 하며, 역시 [[NP-완전]] 문제이다. [[유향 그래프]]에 대한 마찬가지 [[결정 문제]] 역시 [[NP-완전]] 문제이다.
[[
| last = Björklund | first = Andreas
| arxiv = 1008.0541
|