[理工] 104交大資演！（MST)

[Aa841018 (andrew)]

https://i.imgur.com/Jtt4Axj.jpg
請問（b)(c)，（c)我可以理解，但為什麼（b)多了個if就錯了？
然後，詳解我看不是很懂…
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.8.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577066226.A.8DD.html
※ 編輯: Aa841018 (27.246.8.86 臺灣), 12/23/2019 09:57:32
推 gash55025502: 他們的if P then Q的P跟Q是反過來的
推 gash55025502: b可以簡單舉個反例 如三點兩邊權重都1 此時MST唯一
→ gash55025502: 但light edge不唯一
推 gash55025502: c則可以用Prims algorithm去想 在prims回合每個回合
→ gash55025502: 都是挑當下cut權重最小的邊 那既然題目說每個cut此
→ gash55025502: 種邊都唯一 當然造出來的MST也會唯一
推 AirComm: 有人可以翻譯一下b選項嗎？light edge 是啥
推 mistel: 就是橫跨兩個切集權重最小的那個邊
→ Aa841018: 哦！謝謝各位！