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

admin2018-07-17 27

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

美国黑人民权运动在1963年达到高潮，25万黑人和白人在华盛顿林肯纪念堂集会，()发表《我有一个梦想》的演说，这次和平集会和示威标志着争取民权的运动日趋壮大。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

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

氏族公社形成的条件和基本标志是()。

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

1939年5、6月间，英国政府不顾德军的轰炸将33万联军撤到英国，这些部队成为日后反攻的基干，这就是著名的()。

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

国民革命前，中共领导了哪些著名的工人运动?()

下列哪项不是溃疡性结肠炎的常见并发症

患者，男，22岁。乏力、咳嗽、盗汗、低热2个月余，近1周来有咯血及痰中带血。诊断为浸润型肺结核。与感染结核分枝杆菌后是否发病无关的是

经来先期，量多，色淡，质稀；神疲肢倦，小腹空坠，纳少便溏．辨证为经行量多，色紫暗，有血块；伴腹痛，舌质暗，脉涩，辨证为

酪氨酸羟化酶是胆碱乙酰化酶是

生化汤重用全当归为君，意在()

H1受体阻断药可用于治疗

有如下语句序列：charstr［10］;cin>>str;当从键盘输入"Ilovethisgame"时，str中的字符串是()。

在VBA代码调试过程中，能够显示出所有在当前过程中变量声明及变量值信息的是()。