首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
admin
2014-04-17
33
问题
现有一种解决无向连通图的最小生成树的方法:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
下列会议中,讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议
西藏自治区的设立时间是()。
国民政府对日宣战的时间是()。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
苏州的踹工、织工、纸工、烛业工人,景德镇的陶瓷工、门头沟的煤矿工、北京的香工,云南的矿工、广州的织工、陕西的木工和铁工等,均爆发过反对雇主克扣工价、开除工匠和要求增加工银的()斗争。
日本在《二十一条》中提出:“中国沿海岛屿不得租于他国。”其真实目的是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
随机试题
根据门静脉血流受阻的部位,肝内型门静脉高压症可分为________、________和窦型三型。在我国90%以卜的门静脉高压症是由于________引起的________。
肾蒂损伤的特点有()
A.心尖区出现4/6级收缩期吹风样杂音震颤B.发病6个月后心电图ST段持续抬高C.胸骨左缘第四肋间响亮的收缩期吹风样杂音伴震颤D.发病后3天出现心包摩擦音E.交替脉心肌炎可见
环烯醚萜苷具有的性质是
下列防护措施中,()有利于布置路线,减少桥涵。
依次与下列别号正确配对的一组作家是:六一居士北江先生白石道人四明狂客
年轻人小王是一位新人,刚到某处级单位上班。处长鼓励他说:“我们单位所有的年轻人事业上都取得了很大的进步。”副处长则告诫他:“我们单位有的年轻人事业上并没有取得很大的进步!”科长对小王表示欢迎,并介绍说:“我们科所有的年轻人都很勤奋敬业。”同一科的老乡小李则
春秋时期守旧派的代表人物有()。
Writetotheheadofatrain,andcomplainaboutitsbadservices.Youshouldwriteabout100wordsontheANSWERSHEET.Donot
Atsometimeinyourlifeyoumayhaveastrongdesiretodosomethingstrangeorterrible.However,chancesarethatyoudon’t
最新回复
(
0
)