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

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

admin2014-04-17  126
问题 现有一种解决无向连通图的最小生成树的方法：
    将图中所有边按权重从大到小排序为(e1，e2，…，em)；
    i=1；
    while(所剩边数≥顶点数){
    从图中删去ei；
    若图不再连通，则恢复ei；
    i++；
    }
    请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举反例说明。
选项
答案思路分析：要证明最后生成的树是该无向连通图的最小生成树，只需证明以下两点。 (1)n个顶点的连通图的生成树有n—1条边。 (2)所构成的生成树的边的权值之和最小。 结论：该方法可以求得最小生成树。证明如下： 1)从算法中while(所剩边数≥顶点数)可以得出，结束循环的条什是边数比顶点数少1停止，满足n个顶点的连通图的生成树有n—1条边的定义。 2)算法中的“若图不再连通，则恢复ei”含义是必须保留使图连通的边，这就保证了是生成树，甭则就会有同路，或者成为连通分最，都不是生成树。 3)由于边是按权值从大到小排序的，删去的边是权值大的边，结果的生成树必是最小生成树。 综上所述，该办法可以求得无向连通图的最小生成树。 提醒：对于这类题，考生需要对于所证明的概念具有哪种性质极其熟悉，然后根据性质各个击破。对于此题，如果考生连无向连通图的概念都不清楚，那就无从下手。所以，在复习的时候，建议重点抓一些基本概念的特征。
解析
转载请注明原文地址:https://kaotiyun.com/show/zexi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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