如果图 G 具有不同的边成本> 0(即没有两个边成本相同),那么 G 的每个最小瓶颈树是否也是最小生成树?



我的初步答案是肯定的,并通过矛盾证明。

"假设存在G的最小瓶颈树T1和G的最小生成树T2,使得T1不等于T2。这意味着T1的边缘的总重量大于T2的边缘的重量。由于所有边缘成本都是不同的,这意味着T1的瓶颈边缘值必须大于T2的瓶颈边缘。然而,如果这是真的,那么这意味着T2的瓶颈小于T1的瓶颈,这意味着T1不是MBST,这是矛盾的。QED

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

您得出的结论是,">由于所有边缘成本都是不同的,这意味着T1的瓶颈边缘值必须大于T2的瓶颈边缘">这意味着,T1的边缘总权重大于T2的边缘权重。">

总重量是一个总和。一个和可以比另一个大,即使两者都有相同的最大项。所涉及的数字是否不同是无关紧要的。

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

最新更新