作者ooww (選ばれし子どもたち)
看板Math
標題[其他] 最小成本擴張樹(Kruskal)
時間Sun May 23 14:57:35 2021
如圖所示
https://imgur.com/a/stiLyaS
請問第二小題
右邊參考公職王解答，
看不太懂紅色底線的意思，
中間圖樹我依照解答畫出
第6、7點，分支0-3將含4段連線...這段話看不太懂
希望神人解釋
或是可能解答有誤，
跪求神人解惑
我知道Kruskal是依序加入最小邊，但不能有迴圈
可是第二小題條件看不是很懂
願奉上300P感謝幫忙
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.121.236.146 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1621753058.A.122.html
1F：推 RicciCurvatu: 0分出去的任何一條都叫分支 一個分支最多三條線 05/23 15:01
跪求大大可以畫圖幫助我理解
還是聽不太懂
※ 編輯: ooww (122.121.230.234 臺灣), 05/23/2021 16:55:01
2F：推 RicciCurvatu: 0-3-2-1 是一個分支 05/23 17:00
3F：→ RicciCurvatu: 0-4-5-6是一個分支 05/23 17:00
4F：推 LPH66 : 在到 20 那條邊時, 如果加進去則從 0 出發往 3 這邊 05/24 05:48
5F：→ LPH66 : 將有 0-3 3-2 2-1 2-6 四個連線, 不合條件 05/24 05:48
感謝解惑
另外請教您，
題目說起始節點0，
若起始節點改為2或3或4，
結果是否一樣沒變?
※ 編輯: ooww (218.166.99.191 臺灣), 05/25/2021 02:20:29