如何從一組給定路線中查找最小路線集以訪問圖中的所有節點？

從一個給定的圖不一定連接起來，以及一組路徑，其中每個路徑訪問圖中的一組節點。而由兩條不同路徑訪問的節點可能是排他性的，也可能不是唯一的。如何從一組給定路線中查找最小路線集以訪問圖中的所有節點？

有了這些信息，有一種方法可以找到訪問圖中所有節點所需的最少路徑數量？圖論中是否存在一些明確定義的圖論問題，如旅行商，涵蓋了這個問題？如果有的話，請您如此友好地告訴我它的名字是什麼，以便我可以尋找答案。

謝謝

來源

2014-09-24 Rafael Rios

這相當於最小集覆蓋和已知是NP完全問題。請參閱here。

考慮你感興趣的每一條路徑作爲所有圖頂點集合的一個子集，並且你得到同樣的問題。

來源

2014-09-24 17:02:22

對，但你的意思是NP - **硬**，並且要顯示等價性，你必須以另一種方式進行減少：給定任何最小集合覆蓋問題，可以將其轉換爲OP問題的等價實例通過製作具有所有元素集合作爲頂點的完整圖。然後每個覆蓋子集可以通過任意排序其頂點而轉換爲路徑;這總是形成一條路徑，因爲圖形是完整的。 – 2014-09-25 00:21:48

@j_random_hacker在這個特定的問題陳述中，我認爲雙向等價過於明顯，太過描述。無論如何，謝謝你的加入！ – 2014-09-25 07:18:23

好的，但請編輯「NP」到「NP-hard」（或者更好，「NP-complete」）。最小設置覆蓋率是一個NP問題，但增加兩個數字也是一樣！ – 2014-09-25 13:48:10

如何從一組給定路線中查找最小路線集以訪問圖中的所有節點？

回答

相關問題