首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
现有一种解决无向连通图的最小生成树的方法: 将图中所有边按权重从大到小排序为(e1,e2,…,em); i=1; while(所剩边数≥顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i++;
admin
2014-04-17
116
问题
现有一种解决无向连通图的最小生成树的方法:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
下列口号中不是五四运动期间学生在示威游行时高呼的是()。
第一国际成立于下面的哪个城市?()
试总结苏联二三十年代社会主义建设的特点、成就及存在的问题
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
20世纪初,革命派与改良派论战的中心问题是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
世界古代历史上,对东西方文化交流、传播作出突出贡献的是()
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
随机试题
根据下列材料回答问题。2012年Z省W市实现文化及相关产业增加值相比上年增长9.6%,在文化产品制造业中,文化印刷、文化用品制造和工艺美术品制造三大主导行业,2012年分别实现增加值21.82亿元、11.57亿元和6.62亿元。2011年,W
实验观察的要求是()
弗里德曼认为证券、债券收益率越高,其他条件不变,则
进口药品在其它国家和地区发生新的或严重的不良反应,代理经营该进口药品的单位应于不良反应发现之日起
关于结核菌素假阴性反应下列哪种概念是错误的
为避免孔口高程误差造成钻孔灌注桩质量事故,应采取的对策是认真校核原始水准点和各孔口的绝对高程,每根桩钻孔前()。
下面旋律的音乐风格属于()。
一国国际收支顺差会使()。
调用函数时若是引用调用方式,则是将________________。下面所定义的函数f1为值调用方式,函数f2为引用调用方式。若有表达式x=f1(5),则函数调用执行完成后,该表达式中x获得的值为________________。
YouaredoingasurveyonthelifeoftheChinesepeasants.Readthefollowinggraphshowingtheresultsofthesurveyoftheli
最新回复
(
0
)