作者jojoboy0115 (その血の運命~Jo~Jo~)
看板Grad-ProbAsk
標題[理工] 103清大 演算法
時間Sun Jan 20 23:04:33 2019
https://i.imgur.com/UtdQj7X.jpg
https://i.imgur.com/RGYGNzS.jpg
這題敘述的bottleneck spanning tree我感到疑惑
我的理解是這樣
T是bottleneck spanning tree 且為 G 之一 spanning tree
然後下面這句
...be a spanning tree of G whose largest edge weight is
minimum over all spanning trees of G
是翻成
1. G 的最大權重edge為 G 的所有spanning trees 的最小權重
還是
2. T 的最大權重edge為 G 的所有spanning trees 的最小權重
我覺得1不太可能...但是如果是2，答案舉的反例就不符合定義...
該怎麼翻才好...請各位大大指點
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.101.143
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1547996675.A.51B.html
推 yp195126: 2 反例的value 是3 沒有問題 01/20 23:09
→ jojoboy0115: 可是value 3 不是G的最小權重呀? 01/20 23:14
推 yp195126: Value 是TST中最大權重 且是所有st中最大權重的最小值 01/20 23:36
→ yp195126: 設wi是每個st中的最大權重 i=1.2.3.... 則value=min{wi} 01/20 23:38
推 skyHuan: bottleneck ST的定義就是「這棵樹中最大的邊」要是「所 01/21 01:19
→ skyHuan: 有ST中最大的邊」的最小值 01/21 01:19
推 skyHuan: 解答舉例G的3在找ST的時候一定會被挑到，所以每棵ST的最 01/21 01:23
→ skyHuan: 大邊都是3，這樣T的最大邊是3，沒有其他ST的最大邊超過3 01/21 01:23
→ skyHuan: ，所以T可以當bottleneck ST沒問題，但他並不是MST 01/21 01:23
→ jojoboy0115: 原來如此，我懂了！謝謝兩位大大 01/21 14:13