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

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

admin2013-07-12  84
问题 现有一个解决无向连通图的最小生成树的一种方法如下：
将图中所有边按权重从大到小排序为(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
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)