最小生成樹如何顯示重疊的子問題屬性

Question

最小生成樹問題有兩個重疊的子問題 和最佳子結構。

我理解了聲明的第二部分，因爲如果我們考慮MST的兩個子樹，那麼連接它們的最小權重的邊也在MST中。

但我不明白它是如何顯示重疊 - subproblems屬性，請有人解釋它？

Answer 1

要查看子問題 - 即子圖 - 對於MST問題，必須通過刪除邊來劃分圖。沿着所有可能的邊緣取出方式，你會遇到類似的問題（即，相同的子問題），例如，如果您反轉訂單，您可以得到相同的圖形，其中您刪除了幾條邊。因此，如果您探索細分問題的所有方法，您將遇到重疊的子問題。

（當然，我希望我們同意這不是去尋找一個最小生成樹的方式。我嚴格地描述細分的重疊。）