首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
admin
2012-06-26
78
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(el,e2,…,em);
i=1;
while(所剩边数>=顶点数){
从图中删去ei;
若图不再连通。则恢复ei;
i=i+1;
}
请问上述方法能否求得原图的最小生成树?若该方法可行,请证明之;否则请举例说明。
选项
答案
题目中方法能求得最小生成树。证明如下: (1)从算法中while(所剩边数≥顶点数)来看,循环到边数比顶点数少1(即n一1)停止,这符合n个顶点的连通图的生成树有n一1条边的定义; (2)由于边是按权值从大到小排序,删去的边是权值大的边,结果的生成树必是最小生成树; (3)算法中“若图不再连通,则恢复ei”,含义是必须保留使图连通的边,这就保证了是生成树,否则或者是有回路,或者成了连通分量,均不再是生成树。所以,题目中方法可以求得图的最小生成树。
解析
无向连通图的生成树包含图中全部n个顶点,以及足以使图连通的n—l条边。而最小生成树则是各边权值之和最小的生成树。所以要证明题目中的方法正确,需要从以下方面证明,即:n个顶点的连通图的生成树有n一1条边;所构成的生成树的边的权值之和最小。
转载请注明原文地址:https://kaotiyun.com/show/Gyxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
西汉诸侯国的政权机构和中央基本上相同,其中需要中央直接任命的有()
邓小平在同江泽民等谈话时提出的中国社会主义农业改革和发展的“两个飞跃”是()。
第一次世界大战后。《凡尔赛条约》规定了国际联盟管理15年的德国地区是()。
()是宋代为支付军政费用而筹措的一宗款项,同时又是各地为筹措这项经费而加征的苛捐杂税的总名称。
我国第一部系统的史学理论著作是()。
“文化大革命”发动的两个纲领性文件是()。
下列著作不属于被后世称为清代汉学的“不祧祖先”之人的作品的是()
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭重创
詹天佑自主设计修建了中国第一条铁路是在()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
随机试题
现代维修企业应积极推行5S管理,即_______、_______、_______、_______、_______。
根据关系的稳定程度,可将公众分为()
恶寒发热同时并见多见于
通过人体电流的大小取决于
患者,男,42岁,心悸失眠,虚烦,咽干,盗汗,脉细数。用药宜选
个人将其所得通过中国境内的社会团体、国家机关向教育和其他社会公益事业以及遭受严重自然灾害的地区、贫困地区捐赠,捐赠额未超过纳税义务人申报的应纳税所得额的( )的部分可以从其应纳税所得额中扣除。
甲公司主营电池生产业务,现已研发出一种新型锂电池产品,准备投向市场。为了评价该锂电池项目,需要对其资本成本进行估计。有关资料如下:(1)该锂电池项目拟按照资本结构(负债/权益)30/70进行筹资,税前债务资本成本预计为7:11%。(2)
全国各地以鸡为原料的菜中有很多名菜,如叫化鸡、太爷鸡、麻辣仔鸡,上述三道菜所属的菜系依次是( )。
根据我国《刑事诉讼法》的规定,法定的强制措施不包括()。
A、Thereallyneedystudentscan’tgetitandhavetodropout.B、Negotiationsleaveschoolslittleroomforimprovement.C、Stude
最新回复
(
0
)