[理工] 演算法圖論 交大

[qaswed101 (一一)]

https://i.imgur.com/cb0pmoj.jpg

其實這題我不太明白題意但是主要想問
第一小題的a和c選項
我以為這兩個選項是一樣的意思就一起刪掉了
想請問這個觀念

謝謝～

還有一題
https://i.imgur.com/DQ4ZYi3.jpg
我不太明白b的說法有什麼錯誤或是有沒有反例
我雖然知道他要改成c的說法，但不知道b錯什麼

謝謝大家！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.178.181
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511716294.A.AF9.html
推 TMDTMD2487: 就是正邊的最短路徑搜尋，選一個最恰當的選項就是c了
→ TMDTMD2487: 最佳的演算法是dijstra's是用greedy的策略
→ TMDTMD2487: a那個我記得是只可以用dp的結構
推 TMDTMD2487: 第二個問題你直接假設一顆樹所有邊權重都一樣，這樣他
→ TMDTMD2487: 的最小生成數唯一(就是自己)，但邊都一樣所以cut的最
→ TMDTMD2487: 小邊不唯一
推 TMDTMD2487: 所以這裡你可以記得，對於最小生成樹唯一這件事，任
→ TMDTMD2487: 何cut最小邊唯一是他的充分但不必要
推 FRAXIS: 如果圖是樹 ，那任一 cut 頂多只有一條 cross edge?
推 FRAXIS: 沒事 我搞錯了 cut set 不一定要 connected
→ hank292: 因為除了optimal substructure外，此問題具有greedy choi
→ hank292: ce property