首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
admin
2014-04-17
105
问题
现有一种解决无向连通图的最小生成树的方法:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
汉武帝时,为太常博士的弟子兴建学校,名为(),学生入学后免除本人的徭役,学成经考试后,
1928年2月召开的国民党二届四中全会,规定()为国民政府军政最高机关。
玛雅人的金字塔主要功能是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
以下不属于国民党控制金融的“四行”的是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
美国主张建立国际联盟的主要目的是()。
印加人记载事物使用的方法是()。
随机试题
电动机外加电压的变化,对电动机的出力()。
《幼儿园工作规程》规定,幼儿园每日户外活动时间不得少于()
天津的一项调查发现,98%的高校生和92%的小学生都把周末用来做作业。请根据这个调查说明你的看法,写一篇150词左右的英文短文。
光镜下判断细胞是否坏死,主要观察
符合流行性乙型脑炎的描述是
在神经一骨骼肌接头处,消除乙酰胆碱的酶是
目前全世界出版的中医药文献的文字有()
在无权代理的情况下,由( )承担法律责任。
将会计凭证划分为原始凭证和记账凭证的依据是会计凭证()。
某大学生某课程期中得分为75分,期末得分为85分。期中、期末成绩的比为3:7。该大学生学期总平均数是
最新回复
(
0
)