首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
admin
2018-07-17
65
问题
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。
试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
选项
答案
连通图的生成树包括图中的全部n个顶点和足以使图连通的n_1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n—1条边为止。 [*] 这种方法是正确的。由于经过“破圈法”之后,最终没有回路,故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T,假设T不是最小生成树,则必然存在最小生成树T
0
,使得它与T的公共边尽可能地多,则将T
0
与T取并集,得到一个图,此图中必然将存在回路,由于破圈法的定义就是从回路中去除权最大的边,此时生成的T的权必然是最小的,这与原假设T不是最小生成树矛盾。从而T是最小生成树。上图是通过实例来说明“破圈法”的过程。
解析
转载请注明原文地址:https://kaotiyun.com/show/IfRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列标志着周王室在春秋时代的地位一落千丈,仅存虚名的选项是()
七七事变爆发后,()给中国以巨大的支援,双方签订了(),在政治上给中国以重大支持。
有人说,巴黎和会是一次分赃会议,下列《凡尔赛和约》中哪一方面的内容最能体现这一性质?()。
1891年标志着电机发展新阶段开始的是在电能实际应用中首次采用()。
()标志着二战中苏德战场转折的完成。
1939年5、6月间,英国政府不顾德军的轰炸将33万联军撤到英国,这些部队成为日后反攻的基干,这就是著名的()。
无产阶级登上历史舞台的主要标志是()。
纳粹德国公开撕毁《凡尔赛和约》的步骤有()。①大量扩展陆军,重建空军,建造军舰②迫害犹太人③退出国联④开进莱茵非军事区
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
随机试题
肺性脑病不能用高浓度吸氧的主要原因是
男性,35岁,受凉后自感左耳后疼痛,2日后,发现左眼闭合不全,额纹消失,口角歪斜,露齿时偏向右侧,乳突部有压痛,最可能的诊断是
肉毒毒素的作用部位是A.脊髓前角B.脊髓后角C.外周神经-肌肉接头处D.呕吐中枢E.血管内皮
A.肠毒素B.细胞毒素C.神经毒素D.内毒素E.类毒素
下列水泥中,()水泥的水化热较大。
“三全管理”是指________。
材料一:2004年11月14日至21日,亚太经合组织(APEC)高官会议、部长级会议、领导人非正式会议在智利首都圣地亚哥召开,会议的主题是——“一个大家庭,我们的未来”。中美俄等21个经济体的领导人均参加了会议,他们就亚太地区贸易和投资的自由化和便利化、地
设函数f(x)连续,f’(0)>0,则存在δ>0,使得
中国坚持走立足本国国情的和平发展道路,这一道路已经显示出其世界意义,包括
软件生存周期中,解决软件“做什么”的阶段是
最新回复
(
0
)