2
특정 그래프에 해밀턴 경로가 있는지를 결정할 수있는 오라클이 있다고 가정 해 보겠습니다. (주의 사항 : 해밀턴 경로 문제는 NPC에 있습니다.)오라클 머신을 사용하여 다항식 시간에서 해밀턴 경로 찾기
오라클을 사용하여 해밀턴 경로를 다항식 시간으로 찾아내는 방법을 설명하십시오.
아이디어가 있으십니까?
A
답변
3
해밀턴 경로는 모든 정점을 정확히 한 번 방문합니다.
오라클이있는 경우 차례대로 각 가장자리를 제거 할 수 있습니다. 오라클에 아직 경로가 있다고 표시되면 가장자리를 지우십시오. 그렇지 않으면 가장자리를 복원하고 다음 경로를 시도하십시오.
일단 모든 모서리를 통과했다면 남은 것은 모두 해밀턴 경로입니다.
+0
이해할 수 있는지 잘 모르겠습니다. 우리가 차례대로 각 모서리를 제거 할 수 있다고 말하면 - 내가 갖고있는 그래프에서 모서리를 반드시 제거 할 수 있다는 것을 어떻게 알 수 있습니까? 어떤 그래프에서는 가장자리를 없애더라도 해밀턴 경로가 존재하지 않을 가능성이 있습니다. 그렇다면 우리는 왜 가장자리를 제거합니까? – SKriheli
+0
아이디어는 가장자리가 많은 그래프로 시작한다는 것입니다. 오라클은 해밀턴 경로가 있음을 알려주지 만 그것이 어디에 있지는 않습니다. 경로를 유지하면서 가장자리를 제거하여 가능한 한 그래프를 단순화하려고합니다. 가장자리 제거가 끝나면 해밀턴 경로와 동일한 매우 간단한 사슬 그래프를 갖게됩니다. 때때로 가장자리를 제거하면 경로가 제거되는 경우가 있지만이 경우 다시 가장자리를 놓고 다른 가장자리를 시도하는 것이 옳습니다. –
+0
그래서 오라클은 실제로이 그래프가 해밀턴 경로를 포함하고 있음을 알고 있지만 많은 부분이있는 그래프를 얻습니다. 설명대로 가장자리를 제거하면 해밀턴 경로의 일부인 가장자리 만 그래프에 남습니다. 권리? – SKriheli
1
그래프에 n-1 개의 가장자리가 있으면 완료됩니다 (체인이어야 함, 그렇지 않으면 해밀턴 경로가 없음).
그렇지 않으면 가장자리를 삭제할 수 있습니다. 모든 가장자리를 반복 해 봅시다. 고정 에지가없는 그래프에 여전히 경로가있는 경우이를 제거하고 계속 진행할 수 있습니다.
이 솔루션은 O (m^2) 오라클 쿼리가 필요하므로 다항식 시간에 작동합니다.
이것은 컴퓨터 과학 스택 교환 (Computer Science Stack Exchange)에 더 적합 할 수 있습니다. 프로그래밍에 관한 것이 아닙니다. –