下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。试判断这种方法是否正确。如果正确，请说明理由，如果不正确，举出反例(注：圈就是回路)。

admin2018-07-17 82

问题下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
试判断这种方法是否正确。如果正确，请说明理由，如果不正确，举出反例(注：圈就是回路)。

选项

答案连通图的生成树包括图中的全部n个顶点和足以使图连通的n_1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n—1条边为止。 [*] 这种方法是正确的。由于经过“破圈法”之后，最终没有回路，故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T，假设T不是最小生成树，则必然存在最小生成树T₀，使得它与T的公共边尽可能地多，则将T₀与T取并集，得到一个图，此图中必然将存在回路，由于破圈法的定义就是从回路中去除权最大的边，此时生成的T的权必然是最小的，这与原假设T不是最小生成树矛盾。从而T是最小生成树。上图是通过实例来说明“破圈法”的过程。

解析

转载请注明原文地址:https://kaotiyun.com/show/IfRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

七七事变爆发后，()给中国以巨大的支援，双方签订了()，在政治上给中国以重大支持。

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

无产阶级登上历史舞台的主要标志是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

设A为m×n阶矩阵，C为n阶矩阵，B＝AC，且r(A)＝r，r(B)＝r1，则()．

男，25岁，反复右下腹痛、腹泻4年，无黏液脓血便，结肠镜检查发现右半结肠呈节段性炎症改变。该患者选做下列哪项检查最适宜

A．大黄B．枳壳C．黄精D．玫瑰花E．黄连表面具有麻点的药材是

某医生拟选择适当资料，计算指标，进行t检验。

基底原状土的强度不符合要求时，应进行()。

下列各项中，超过税法规定的扣除限额部分，可以结转到以后年度扣除的有()。

学生学习知识不是靠教师讲解，而是通过自己的新旧知识相互作用而形成的建构。这是()的观点。

《关于公立医院改革试点的指导意见》明确提出，公立医院要以()为核心，逐步取消药品加成，增设药事服务费，该项费用纳入医保。