0
이 paper은 블록 그래프 또는 2 부분 순열 그래프의 최적 경로 커버 문제를 해결합니다. 소개의 세 번째 줄에서는 최적의 경로 커버 문제는 NP-Complete이며 "컴퓨터 및 다루기 힘든 부분 : David S. Johnson, Michael R. Garey의 NP 완전성 이론 안내서"를 참조했습니다. 그러나 나는 그 책에서 그 증거를 찾을 수 없었다. 누구든지이 문제의 NP-Completeness를 입증하는 방법을 알고 있다면 솔루션을 공유하십시오.최적 경로 커버의 NP 완전성 증명.
최적 경로 커버 문제점 :
그래프 G 감안할 함께 그래프의 모든 꼭지점을 커버 정점 이산 경로의 최소 수를 찾는. 명백한 결정 변형 고려
@ D.W. 이 질문은 다른 질문과 완전히 다릅니다. 뭐하고 있니? –
네 말이 맞아, 내 실수 야. –