首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
admin
2018-07-17
82
问题
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。
试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
选项
答案
连通图的生成树包括图中的全部n个顶点和足以使图连通的n_1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n—1条边为止。 [*] 这种方法是正确的。由于经过“破圈法”之后,最终没有回路,故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T,假设T不是最小生成树,则必然存在最小生成树T
0
,使得它与T的公共边尽可能地多,则将T
0
与T取并集,得到一个图,此图中必然将存在回路,由于破圈法的定义就是从回路中去除权最大的边,此时生成的T的权必然是最小的,这与原假设T不是最小生成树矛盾。从而T是最小生成树。上图是通过实例来说明“破圈法”的过程。
解析
转载请注明原文地址:https://kaotiyun.com/show/IfRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
七七事变爆发后,()给中国以巨大的支援,双方签订了(),在政治上给中国以重大支持。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
无产阶级登上历史舞台的主要标志是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
随机试题
设A为m×n阶矩阵,C为n阶矩阵,B=AC,且r(A)=r,r(B)=r1,则().
男,25岁,反复右下腹痛、腹泻4年,无黏液脓血便,结肠镜检查发现右半结肠呈节段性炎症改变。该患者选做下列哪项检查最适宜
A.大黄B.枳壳C.黄精D.玫瑰花E.黄连表面具有麻点的药材是
某医生拟选择适当资料,计算指标,进行t检验。
基底原状土的强度不符合要求时,应进行()。
下列各项中,超过税法规定的扣除限额部分,可以结转到以后年度扣除的有()。
学生学习知识不是靠教师讲解,而是通过自己的新旧知识相互作用而形成的建构。这是()的观点。
某单位内部领导不团结,同事之间纠纷不断,工作几乎处于瘫痪状态,上级部门安排王某到该单位任主任一职,以期改进工作面貌。王某上任后,以身作则,以“苟利国家生死以,岂因福祸避趋之”来鞭策自己,一心想要开创工作新局面,单位同事也对王某抱于很大希望。他一改前任领导专
《关于公立医院改革试点的指导意见》明确提出,公立医院要以()为核心,逐步取消药品加成,增设药事服务费,该项费用纳入医保。
某商场经营管理系统在3点进行了数据库全备份,9点进行了数据库日志备份,10点30分存储数据库数据的磁盘出现故障,但日志保存在另外一个磁盘中。数据库管理员发现问题后随即进行数据恢复工作,在所有备份均可用的情况下,数据库数据可以恢复到的时间点为()。
最新回复
(
0
)