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

admin2018-07-17 22

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

选项

答案连通图的生成树包括图中的全部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万黑人和白人在华盛顿林肯纪念堂集会，()发表《我有一个梦想》的演说，这次和平集会和示威标志着争取民权的运动日趋壮大。

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

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

1891年标志着电机发展新阶段开始的是在电能实际应用中首次采用()。

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

后溪穴属于()。

设函数()

A．急性痢疾B．急性肠炎C．霍乱D．伤寒E．斑疹伤寒属于下列类型疾病的是立克次体病

男，45岁，因上呕下泻住某医院，每天静脉点滴庆大霉素16万单位共9天，近5天来少尿(200～300ml/d)，球结膜水肿，腹水，下肢水肿。实验室检查：血BUN38.6mmol/L,血肌酐1214mmol/L，血清钾6.9mmol/L下列哪项检查对

在进行资产评估时对不同公司投入股份有限公司的同类资产，可以按不同价格标准评估。()

银行业从业人员的下列行为中,属于“反洗钱”规定的有()。

《教师教学课程标准(试行)》强调教师要成为反思性实践者。()

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

请从报道方式的不同、各自的表意功能和符号表意方面的异同等三个方面，来试述文字符号与试听符号的差异。