作者jojoboy0115 (その血の运命~Jo~Jo~)
看板Grad-ProbAsk
标题[理工] 103清大 演算法
时间Sun Jan 20 23:04:33 2019
https://i.imgur.com/UtdQj7X.jpg
https://i.imgur.com/RGYGNzS.jpg
这题叙述的bottleneck spanning tree我感到疑惑
我的理解是这样
T是bottleneck spanning tree 且为 G 之一 spanning tree
然後下面这句
...be a spanning tree of G whose largest edge weight is
minimum over all spanning trees of G
是翻成
1. G 的最大权重edge为 G 的所有spanning trees 的最小权重
还是
2. T 的最大权重edge为 G 的所有spanning trees 的最小权重
我觉得1不太可能...但是如果是2，答案举的反例就不符合定义...
该怎麽翻才好...请各位大大指点
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.233.101.143
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547996675.A.51B.html
1F：推 yp195126: 2 反例的value 是3 没有问题 01/20 23:09
2F：→ jojoboy0115: 可是value 3 不是G的最小权重呀? 01/20 23:14
3F：推 yp195126: Value 是TST中最大权重 且是所有st中最大权重的最小值 01/20 23:36
4F：→ yp195126: 设wi是每个st中的最大权重 i=1.2.3.... 则value=min{wi} 01/20 23:38
5F：推 skyHuan: bottleneck ST的定义就是「这棵树中最大的边」要是「所 01/21 01:19
6F：→ skyHuan: 有ST中最大的边」的最小值 01/21 01:19
7F：推 skyHuan: 解答举例G的3在找ST的时候一定会被挑到，所以每棵ST的最 01/21 01:23
8F：→ skyHuan: 大边都是3，这样T的最大边是3，没有其他ST的最大边超过3 01/21 01:23
9F：→ skyHuan: ，所以T可以当bottleneck ST没问题，但他并不是MST 01/21 01:23
10F：→ jojoboy0115: 原来如此，我懂了！谢谢两位大大 01/21 14:13