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

admin2018-07-17 51

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下面哪部经典是我国最早的官方史书?()

下列标志着周王室在春秋时代的地位一落千丈，仅存虚名的选项是()

有人说，巴黎和会是一次分赃会议，下列《凡尔赛和约》中哪一方面的内容最能体现这一性质?()。

解放战争中标志着中国革命开始由被动转为主动的事件是()。

()标志着二战中苏德战场转折的完成。

纳粹德国公开撕毁《凡尔赛和约》的步骤有()。①大量扩展陆军，重建空军，建造军舰②迫害犹太人③退出国联④开进莱茵非军事区

A、呼吸道传播B、口-口接触传播C、粪一口传播D、血液传播E、虫媒传播EB病毒感染：()

在药品分类管理中国家食品药品监督管理局负责()

下列关于建设工程招标的表述中，错误的是()。

下述对跨度窄、层次多的组织结构的特点描述正确的是()。

在火焰中被燃烧，一定时间内仍能正常运行的电缆是()。

以下属于品种法特征的有()。

在16PF测验中，实验性因素的高分特征也称()。

直观教具可分为()。

某培训基地给一批参训学员分配宿舍。如果每个房间住4人，则有18人没有地方住；如果每个房间住6人，则有2个房间空出来。这批参训学员共有()人。

为了使文本框只具有垂直滚动条，应先把MultiLine属性设置为True，然后再把ScrollBars属性设置为