0

下面引用了这个问题的完整版本:

设 G 是具有 n 个顶点、m 个边具有不同边权重的连通图。设T为G的n个顶点n-1条边的树(即生成树),定义T的瓶颈边为T中权重最小的边。如果不存在具有更大瓶颈边缘的生成树,则最大瓶颈树是 G 的生成树。证明或提供以下陈述的反例:

G 的每个最大生成树都是 G 的最大瓶颈树

我认为由于该图具有唯一的边权重,因此 G 的每个生成树也是唯一的。那么G只有一个最大生成树,如果我能证明这棵树也是一个最大瓶颈树,那么这将证明这个陈述是正确的,但前提是对于所有具有唯一边权重的图都是正确的.

我已经尝试寻找反例来证明这一点是错误的,但到目前为止,看起来我用独特的边权重绘制的每张图最终都有最大生成树也是最大瓶颈树。我想我可以用它来证明这个说法是正确的,但我不知道如何措辞。

4

1 回答 1

0

否定图中的所有边权重。然后问题分别变为最小生成树和最小瓶颈生成树。

现在每个最小生成树也是最小瓶颈生成树。Cut Property 的证明。
http://flashing-thoughts.blogspot.in/2010/06/everything-about-bottleneck-spanning.html

于 2014-12-10T05:08:57.237 回答