[理工] 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