现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2.…,em); i=l; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=i+l;

admin2013-07-12  74

问题 现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(e1,e2.…,em);
    i=l;
    while(所剩边数>=顶点数){
    从图中删去ei;
    若图不再连通,则恢复ei;
    i=i+l;
}
    请问上述方法能否求得原图的最小生成树?若该方法可行,请证明之;否则请举例说明。

选项

答案题目中方法能求得最小生成树。证明如下: (1)从算法中while(所剩边数≥顶点数)来看,循环到边数比顶点数少1(即n-1)停止,这符合n个顶点的连通图的生成树有n-1条边的定义; (2)由于边是按权值从大到小排序,删去的边是权值大的边,结果的生成树必是最小生成树; (3)算法中“若图不再连通,则恢复ei”,含义是必须保留使图连通的边,这就保证了是生成树,否则或者是有回路,或者成了连通分量,均不再是生成树。 所以,题目中方法可以求得图的最小生成树。

解析 无向连通图的生成树包含图中全部n个顶点,以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。所以要证明题目中的方法正确,需要从以下方面证明,即:n个顶点的连通图的生成树有n-1条边;所构成的生成树的边的权值之和最小。
转载请注明原文地址:https://kaotiyun.com/show/1uxi777K
0

随机试题
最新回复(0)