作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] 104交大資演！（MST)
時間Mon Dec 23 09:57:04 2019
https://i.imgur.com/Jtt4Axj.jpg
請問（b)(c)，（c)我可以理解，但為什麼（b)多了個if就錯了？
然後，詳解我看不是很懂…
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.8.86 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577066226.A.8DD.html
※ 編輯: Aa841018 (27.246.8.86 臺灣), 12/23/2019 09:57:32
1F：推 gash55025502: 他們的if P then Q的P跟Q是反過來的 12/23 11:42
2F：推 gash55025502: b可以簡單舉個反例 如三點兩邊權重都1 此時MST唯一 12/23 11:44
3F：→ gash55025502: 但light edge不唯一 12/23 11:44
4F：推 gash55025502: c則可以用Prims algorithm去想 在prims回合每個回合 12/23 11:46
5F：→ gash55025502: 都是挑當下cut權重最小的邊 那既然題目說每個cut此 12/23 11:46
6F：→ gash55025502: 種邊都唯一 當然造出來的MST也會唯一 12/23 11:46
7F：推 AirComm: 有人可以翻譯一下b選項嗎？light edge 是啥 12/23 16:47
8F：推 mistel: 就是橫跨兩個切集權重最小的那個邊 12/23 16:49
9F：→ Aa841018: 哦！謝謝各位！ 12/23 21:47