作者liljimmy (吉米)
看板Grad-ProbAsk
标题[理工] 103清大资工 Bottleneck Spaning Tree问
时间Mon Nov 23 17:06:00 2020
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1606122362.A.4C2.html
1F：→ cossetannie: bottleneck定义就是weight最大的边 11/23 19:19
2F：→ cossetannie: 29题对BST的定义就是MBST啊 11/23 19:22
3F：→ cossetannie: 然後最後那个讲的是MBST不一定是MST 就这样 11/23 19:23
4F：→ cossetannie: 就拿29题的tree来讲好了 所有的spanning tree都会是 11/23 19:26
5F：→ cossetannie: MBST 因为不管怎样选都会选到weight=3的边 11/23 19:26
6F：→ cossetannie: 但MST只会有一个 11/23 19:26
7F：→ liljimmy: 刚刚又查了一下资料，发现Bottleneck spanning tree好 11/23 19:36
8F：→ liljimmy: 像就是指Minimum Bottleneck spanning tree?! 11/23 19:36
9F：→ cossetannie: 题目有写定义啊 11/23 19:38