特定Minimum Spanning Tree的构造问题

bankrock · #1 (**permalink**) 2007-07-22

问题如下：

引用:

Kruskal's algorithm can return different spanning trees for the same input graph G, depending on how ties are broken when the edges are sorted into order. Show that for each minimum spanning tree T of G, there is a way to sort the edges of G in Kruskal's algorithm so that the algorithm returns T.

我的想法是，对于联通图G的MST的某条边L，断开后形成的两个划分之间的所有边的权重的最小值和L的权重相等，那么按我的直觉(-_-)这些权重相等的边应该有排列使Kruskal's algorithm运行时选中L。
只有一个模糊的直觉支撑这个想法，有谁能给个严密的证明么？

Elminster · #2 (**permalink**) 2007-08-30

对于任意的图 G 和它的任意一颗最小生成树 T，可以处理一下 G 的边权（在每条边的权值上加个很小的拖尾数，保证任意两条边权值不同）得到 G'，使得在 G' 上运行 Kruskal 算法必然得到 T ，同时这个加边的次序也是在 G 上运行 Kruskal 算法的一个合法次序。

bankrock · #3 (**permalink**) 2007-09-17

引用:

在每条边的权值上加个很小的拖尾数，保证任意两条边权值不同

是减去把，小的先被选中，思路确实是这样的，多谢烧卖了

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式

相似的主题
主题	主题作者	版面	回复	最后发表
一道directed spanning tree的题	colinzhengj	算法	5	2007-03-19 03:51 PM