首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
admin
2018-07-17
48
问题
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。
试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
选项
答案
连通图的生成树包括图中的全部n个顶点和足以使图连通的n_1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n—1条边为止。 [*] 这种方法是正确的。由于经过“破圈法”之后,最终没有回路,故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T,假设T不是最小生成树,则必然存在最小生成树T
0
,使得它与T的公共边尽可能地多,则将T
0
与T取并集,得到一个图,此图中必然将存在回路,由于破圈法的定义就是从回路中去除权最大的边,此时生成的T的权必然是最小的,这与原假设T不是最小生成树矛盾。从而T是最小生成树。上图是通过实例来说明“破圈法”的过程。
解析
转载请注明原文地址:https://kaotiyun.com/show/IfRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
美国黑人民权运动在1963年达到高潮,25万黑人和白人在华盛顿林肯纪念堂集会,()发表《我有一个梦想》的演说,这次和平集会和示威标志着争取民权的运动日趋壮大。
下列标志着周王室在春秋时代的地位一落千丈,仅存虚名的选项是()
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
氏族公社形成的条件和基本标志是()。
解放战争中标志着中国革命开始由被动转为主动的事件是()。
()标志着二战中苏德战场转折的完成。
()标志着二战中苏德战场转折的完成。
1939年5、6月间,英国政府不顾德军的轰炸将33万联军撤到英国,这些部队成为日后反攻的基干,这就是著名的()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
随机试题
组织文化的()主要是指对组织成员的价值取向及行为取向所起的引导作用。
先天性心脏病姑息性手术中主一肺动脉分流术。其临床效果是
男性,16岁,骤起严重水肿入院,血压正常,腹水征(+),尿蛋白(++++),红细胞0一2个/HP,24小时尿蛋白定量6g,血CT100μmol/L,血C3、CH50正常,血白蛋白24g/L,入院后予泼尼松每日40mg口服,2周后肾活检示:肾小球系
"疳者甘也",是指"疳者干也",是指
A.气滞血瘀B.气不摄血C.气随血脱D.气血两虚E.气血失和肝病日久,两胁胀满疼痛,并见舌质瘀斑、瘀点。其病机是()
张某以自己的房产向保险人投保,确定该房产的价值为100万元,由于地震该房屋开裂,评估其重置净值为60万元,损失比例为50%,则赔偿金额为()万元。
企业发生的下列事项中,不影响“投资收益”科目金额的有()。
我国现行税法规定,对外经济合作企业承揽中国政府援外项目,获得当地国家政府减免所得税的,经税务机关审核后,视同已经缴纳企业所得税进行抵免。()
某车间为了提高产品合格率,由几名技术人员和工人组成一个QC小组。接着,小组就弯曲和损伤这两项主要不合格类型的原因进行分析,绘制了因果图。有个组员说因果图还有其他名称,它又称作()。
简述夫妻约定财产制的主要内容。
最新回复
(
0
)