0
주어진 그래프에서 반드시 연결되어있는 것은 아니며 각 경로는 그래프의 노드 집합을 방문하는 경로 집합입니다. 두 개의 다른 경로로 방문한 노드는 배타적 일 수도 있고 아닐 수도 있습니다.주어진 경로 집합에서 그래프의 모든 노드를 방문하는 최소 경로 집합을 찾는 방법은 무엇입니까?
그 정보로 그래프의 모든 노드를 방문하는 데 필요한 최소 경로 수를 찾는 방법이 있습니까? 이 문제를 다루는 여행 세일즈맨처럼 그래프 이론에 잘 정의 된 문제가 있습니까? 답을 찾을 수 있도록 이름이 무엇인지 말해 주시면 친절하십니까?
감사
맞아요,하지만 당신은 NP - ** 하드 **를 의미하고, 등가성을 보여주기 위해서 당신은 다른 방식으로 축소를해야합니다 : 최소한의 세트 커버 문제가 있다면, 이것을 OP 문제의 동등한 인스턴스로 변환 할 수 있습니다 모든 요소들의 집합을 정점들로 갖는 완전한 그래프를 만들어라. 그런 다음 각각의 커버링 부분 집합은 정점을 임의로 정렬하여 경로로 변환 할 수 있습니다. 그래프가 완성 되었기 때문에 항상 경로를 형성합니다. –
@j_random_hacker이 특정 문제에 대한 진술 나는 양방향 동등성이 너무 명확해서 너무 설명하기 힘들다고 생각했다. 어쨌든, 추가 주셔서 감사합니다! –
OK, "NP"를 "NP-hard"(또는 "NP-complete")로 편집하십시오. 최소 세트 커버는 NP 문제이지만 두 개의 숫자도 추가됩니다! –