首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
admin
2014-04-17
101
问题
现有一种解决无向连通图的最小生成树的方法:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
新经济政策的实施表明苏俄()①放弃了由战时共产主义政策过渡到社会主义的设想②发展了马克思主义理论③适时调整生产关系以适应生产力发展④利用市场和商品货币关系发展经济
我国第一部系统的史学理论著作是()。
系统阐明社会主义初级阶段理论是在()。
英国发动鸦片战争的主要目的是()。
蒙古军西征之后,罗斯处于()的控制之下。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参与预政事,并受封为侯,这是宦官用权和封侯的开始。
西南军阀跟随孙中山拥护护法运动的目的是()。
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
随机试题
Thepopulationhad______fromabout8,300,000in1845tolessthan6,600,000.
关于破伤风痉挛毒素的特性正确的是
雌激素和孕激素协同作用的表现是
引起咽结合膜热的病原体是柯萨奇病毒。()
朝秦暮楚,见异思迁,虎头蛇尾等指意志的()。
读图1,美国农业带的分布,其中④区域是()。
民事行为能力不是从人一出生就有的。()
Writealettertoatravelagency,askingaboutthedetailedinformationaboutapackagetour.Youshouldincludethedetailsyo
下列说法错误的是()。
给定程序中,函数fun的功能是:计算下式前n项的和作为函数值返回。例如,当形参n的值为10时,函数返回:-0.204491。请在程序的下划线处填入正确的内容并把下划线删除,使程序得出正确的结果。注意:源程序存放在考生文件夹下的BLANK1.C中。
最新回复
(
0
)