作者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