https://i.imgur.com/cb0pmoj.jpg
其實這題我不太明白題意但是主要想問
第一小題的a和c選項
我以為這兩個選項是一樣的意思就一起刪掉了
想請問這個觀念
謝謝～
還有一題
https://i.imgur.com/DQ4ZYi3.jpg
我不太明白b的說法有什麼錯誤或是有沒有反例
我雖然知道他要改成c的說法，但不知道b錯什麼
謝謝大家！

就是正邊的最短路徑搜尋，選一個最恰當的選項就是c了最佳的演算法是dijstra's是用greedy的策略a那個我記得是只可以用dp的結構第二個問題你直接假設一顆樹所有邊權重都一樣，這樣他的最小生成數唯一(就是自己)，但邊都一樣所以cut的最小邊不唯一所以這裡你可以記得，對於最小生成樹唯一這件事，任何cut最小邊唯一是他的充分但不必要

如果圖是樹 ，那任一 cut 頂多只有一條 cross edge?沒事 我搞錯了 cut set 不一定要 connected

因為除了optimal substructure外，此問題具有greedy choice property