[理工] 103清大資工 Bottleneck Spaning Tree問

[liljimmy (吉米)]

https://i.imgur.com/NCTrXUy.jpg

https://i.imgur.com/i0AcqvV.jpg

想請問各位，Bottleneck spanning tree（簡稱BST)是指什麼呢..？有查過相關資料但還是
不能理解，所以又上來問，非常抱歉。

目前猜測是BST是指一張圖所有spinning tree（含有最大權重的邊）都稱為BST，不知道對
不對。

還有一個問題是Minimum bottleneck spanning tree(簡稱MBST）又是指什麼呢？
看其他篇的高手解答是說一張圖所有spnning tree取最大權重邊為最小的那個叫MBST所以可
能很多種，這樣理解也不知道對不對...

又查到了一個網站的介紹：
https://i.imgur.com/aUnnlrQ.png

其中提到：The Minimum Bottleneck Spanning trees for the graph are the trees with
 bottleneck edge weight 3. Here, the minimum spanning tree is a minimum bottlene
ck spanning tree but not all minimum bottleneck spanning trees are not minimum s
panning trees.
但我看他指的MBST並不是我理解”的所有MST中取最大權重為最小的那個MST”，然後他又說
這張圖的MST又剛好是MBST...？

我講的很亂但只好把我目前理解的都打出來了，求各位解答感謝。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.40.232 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1606122362.A.4C2.html
→ cossetannie: bottleneck定義就是weight最大的邊
→ cossetannie: 29題對BST的定義就是MBST啊
→ cossetannie: 然後最後那個講的是MBST不一定是MST 就這樣
→ cossetannie: 就拿29題的tree來講好了 所有的spanning tree都會是
→ cossetannie: MBST 因為不管怎樣選都會選到weight=3的邊
→ cossetannie: 但MST只會有一個
→ liljimmy: 剛剛又查了一下資料，發現Bottleneck spanning tree好
→ liljimmy: 像就是指Minimum Bottleneck spanning tree?!
→ cossetannie: 題目有寫定義啊