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

admin2018-07-17 48

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

选项

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

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

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

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

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

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

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

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

组织文化的()主要是指对组织成员的价值取向及行为取向所起的引导作用。

先天性心脏病姑息性手术中主一肺动脉分流术。其临床效果是

男性，16岁，骤起严重水肿入院，血压正常，腹水征(+)，尿蛋白(++++)，红细胞0一2个／HP，24小时尿蛋白定量6g，血CT100μmol／L，血C3、CH50正常，血白蛋白24g／L，入院后予泼尼松每日40mg口服，2周后肾活检示：肾小球系

"疳者甘也"，是指"疳者干也"，是指

A．气滞血瘀B．气不摄血C．气随血脱D．气血两虚E．气血失和肝病日久，两胁胀满疼痛，并见舌质瘀斑、瘀点。其病机是()

张某以自己的房产向保险人投保，确定该房产的价值为100万元，由于地震该房屋开裂，评估其重置净值为60万元，损失比例为50％，则赔偿金额为()万元。

企业发生的下列事项中，不影响“投资收益”科目金额的有()。

我国现行税法规定，对外经济合作企业承揽中国政府援外项目，获得当地国家政府减免所得税的，经税务机关审核后，视同已经缴纳企业所得税进行抵免。()

某车间为了提高产品合格率，由几名技术人员和工人组成一个QC小组。接着，小组就弯曲和损伤这两项主要不合格类型的原因进行分析，绘制了因果图。有个组员说因果图还有其他名称，它又称作()。

简述夫妻约定财产制的主要内容。