如果图G具有不同的边成本> 0（即，没有两个边成本相同），则G的每个最小瓶颈树是否也是最小生成树？

Question

我最初的回答是肯定的，并有矛盾的证明。

“假设存在G的最小瓶颈树T1和G的最小生成树T2，使得T1不等于T2。这意味着T1的边的总权重大于T1的边的权重T2。由于所有边缘成本都是不同的，因此这意味着T1的瓶颈边缘值必须大于T2的瓶颈边缘值。但是，如果这是真的，则意味着T2的瓶颈小于T1的瓶颈，这意味着T1不是MBST，这是一个矛盾。QED。

[我知道边缘成本不是唯一的，那么答案是否定的，MBST不一定是MST，但是如果边缘成本是唯一的，我相信这会改变事情。

Answer 1

您在逻辑上取得了一个飞跃的结论，“ 由于所有边缘成本都是不同的，这意味着T1的瓶颈边缘值必须大于T2的瓶颈边缘值” from“ 这意味着边缘的总权重T1的权重大于T2的边缘权重。“

总重量为总和。即使两项的最大期限相同，一笔款项也可能大于另一笔款项。所涉及的数字是否唯一无关紧要。

寻找一个具有4个顶点和4个边的小反例。

Answer 2

没有这是一个反例：

{(1, 2), (2, 4), (3, 4)}给出了一个可能的最小生成树，其权重为5 + 5 + 1 = 11。但是，{(1, 2), (1, 3), (2, 4)}给出了可能的最小瓶颈生成树，其权重为5 + 5 + 5 = 15 > 11。