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

看板Grad-ProbAsk作者 (andrew)時間6年前 (2019/12/23 09:57), 6年前編輯推噓5(5推 0噓 4→)
留言9則, 4人參與, 6年前最新討論串1/1
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
推
12/23 11:42, 6年前 , 1F
他們的if P then Q的P跟Q是反過來的
12/23 11:42, 1F
推
12/23 11:44, 6年前 , 2F
b可以簡單舉個反例 如三點兩邊權重都1 此時MST唯一
12/23 11:44, 2F
→
12/23 11:44, 6年前 , 3F
但light edge不唯一
12/23 11:44, 3F
推
12/23 11:46, 6年前 , 4F
c則可以用Prims algorithm去想 在prims回合每個回合
12/23 11:46, 4F
→
12/23 11:46, 6年前 , 5F
都是挑當下cut權重最小的邊 那既然題目說每個cut此
12/23 11:46, 5F
→
12/23 11:46, 6年前 , 6F
種邊都唯一 當然造出來的MST也會唯一
12/23 11:46, 6F
推
12/23 16:47, 6年前 , 7F
有人可以翻譯一下b選項嗎？light edge 是啥
12/23 16:47, 7F
推
12/23 16:49, 6年前 , 8F
就是橫跨兩個切集權重最小的那個邊
12/23 16:49, 8F
→
12/23 21:47, 6年前 , 9F
哦！謝謝各位！
12/23 21:47, 9F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1U01xoZT (Grad-ProbAsk)