首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2.…,em); i=l; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=i+l;
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2.…,em); i=l; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=i+l;
admin
2013-07-12
59
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(e1,e2.…,em);
i=l;
while(所剩边数>=顶点数){
从图中删去ei;
若图不再连通,则恢复ei;
i=i+l;
}
请问上述方法能否求得原图的最小生成树?若该方法可行,请证明之;否则请举例说明。
选项
答案
题目中方法能求得最小生成树。证明如下: (1)从算法中while(所剩边数≥顶点数)来看,循环到边数比顶点数少1(即n-1)停止,这符合n个顶点的连通图的生成树有n-1条边的定义; (2)由于边是按权值从大到小排序,删去的边是权值大的边,结果的生成树必是最小生成树; (3)算法中“若图不再连通,则恢复ei”,含义是必须保留使图连通的边,这就保证了是生成树,否则或者是有回路,或者成了连通分量,均不再是生成树。 所以,题目中方法可以求得图的最小生成树。
解析
无向连通图的生成树包含图中全部n个顶点,以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。所以要证明题目中的方法正确,需要从以下方面证明,即:n个顶点的连通图的生成树有n-1条边;所构成的生成树的边的权值之和最小。
转载请注明原文地址:https://jikaoti.com/ti/qwajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
当代科技革命说明:作为第一生产力的(),是推动现代生产力发展的最活跃因素,并且是现代社会进步的决定性力量。
在1957年反右派运动严重扩大化过程中采取的错误斗争方式包括()。
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
论述新石器时代及其文化类型。
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
中古时代实行索贡巡行赋税征收方式的国家是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
有关石油的最早记载者是()
在民主革命取得全国性胜利并完成土地革命后,中国国内存在的主要矛盾是()。
下列选项中,操作系统提供给应用程序的接口是____。
随机试题
代理的种类有()
规划环境影响评价应尽可能在规划编制的()介入,并将对环境的考虑充分融入规划中。
建设工程项目()的费用增加与信息交流存在的问题有关。
甲公司为一家ST公司,该公司内部审计部门在对其2×17年度财务报表进行内审时,对以下交易或事项的会计处理提出疑问:(1)2×17年3月31日,甲公司应收乙公司账款余额为122万元,已提坏账准备20万元,因乙公司发生财务困难,双方进行债务重组。2×17
学生小谭写作业的速度比较慢,做作业时注意力不集中,而且注意力很容易被其他轻微刺激所吸引,妈妈为此非常苦恼。这时,我们定出的目标行为是:提高孩子做作业的速度和质量。我们在孩子做作业的地方放上一个钟,让孩子时刻注意到自己做作业的速度,在孩子的手腕上套上一个皮筋
执法人员当场作出行政处罚决定的,应当向当事人出示执法身份证件,填写预定格式、编有号码的行政处罚决定书。行政处罚决定书应当当场交付当事人。()
Mywatchdoesn’twork.Imusthaveit______tomorrow.
A、Violence.B、Compromise.C、Firearms.D、Police.B本题设题点在对话问答处。访谈中提到,英国不是:暴力社会,根据句(7—1)和句(7—2)可知,英国人喜欢和解而不是暴力相向,故答案为[B]。
A、Buyanewcar.B、Decoratehishouse.C、Seeadoctor.D、Readabook.B女士称赞男士的新家很漂亮,男士表达了谢意,并表示还需要一些装饰。由此可见,男士打算装饰他的房子。
Housingofficialssaythatlatelytheyarenoticingsomethingdifferent:studentsseemtolackthewill,andskill,toaddresst
最新回复
(
0
)