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

作者: liljimmy (吉米)   2020-11-23 17:06:00
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...?
我講的很亂但只好把我目前理解的都打出來了,求各位解答感謝。
作者: cossetannie (paa)   2020-11-23 19:19:00
bottleneck定義就是weight最大的邊29題對BST的定義就是MBST啊然後最後那個講的是MBST不一定是MST 就這樣就拿29題的tree來講好了 所有的spanning tree都會是MBST 因為不管怎樣選都會選到weight=3的邊但MST只會有一個
作者: liljimmy (吉米)   2020-11-23 19:36:00
剛剛又查了一下資料,發現Bottleneck spanning tree好像就是指Minimum Bottleneck spanning tree?!
作者: cossetannie (paa)   2020-11-23 19:38:00
題目有寫定義啊

Links booklink

Contact Us: admin [ a t ] ucptt.com