首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。 试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
admin
2018-07-17
76
问题
下面有一种称为“破圈法”的求解最小生成树的方法:所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。
试判断这种方法是否正确。如果正确,请说明理由,如果不正确,举出反例(注:圈就是回路)。
选项
答案
连通图的生成树包括图中的全部n个顶点和足以使图连通的n_1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n—1条边为止。 [*] 这种方法是正确的。由于经过“破圈法”之后,最终没有回路,故一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T,假设T不是最小生成树,则必然存在最小生成树T
0
,使得它与T的公共边尽可能地多,则将T
0
与T取并集,得到一个图,此图中必然将存在回路,由于破圈法的定义就是从回路中去除权最大的边,此时生成的T的权必然是最小的,这与原假设T不是最小生成树矛盾。从而T是最小生成树。上图是通过实例来说明“破圈法”的过程。
解析
转载请注明原文地址:https://kaotiyun.com/show/IfRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
美国黑人民权运动在1963年达到高潮,25万黑人和白人在华盛顿林肯纪念堂集会,()发表《我有一个梦想》的演说,这次和平集会和示威标志着争取民权的运动日趋壮大。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
下面哪部经典是我国最早的官方史书?()
解放战争中标志着中国革命开始由被动转为主动的事件是()。
1939年5、6月间,英国政府不顾德军的轰炸将33万联军撤到英国,这些部队成为日后反攻的基干,这就是著名的()。
无产阶级登上历史舞台的主要标志是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
随机试题
劳动争议仲裁原则上是劳动争议诉讼的前提,且大多数劳动争议仲裁裁决并非一裁终局,当事人不服裁决的,可以________________。
以下属于操作系统的是__________。()
判断肺痈溃脓期逆症的表现有
激光打印机中,激光束对胶片完成“幅式打印”的部件是
当外界环境中气温高于皮肤温度时人体散热主要靠
根据确认的竣工结算报告,承包商向业主申请支付工程竣工结算款。业主应在收到申请后()天内支付结算款,到期没有支付的应承担违约责任。
图示结构,已知L=4m,q=6kN/m,M=8kN.m,则A处的约束反力偶为()。
2005年1月5日,甲上市公司接受其关联方——丙公司的委托,经营丙公司的一全资子公司——A公司。A公司2005年初的账面净资产为10000万元。按托管协议规定,甲公司受托经营A公司4年,甲公司每年可获取800万元的固定收益。假定A公司2005年度实现净利润
政府网站应成为政府信息公开的重要载体,但是有的政府网很少能成为老百姓浏览并解决实际问题的有效途径。解决上述问题的关键是我们的政府要()。
A、Itcanbeacquiredfromseafood.B、Itisgoodforourbonesandteeth.C、Itismainlyconsumedbyvegetarians.D、Itisnotas
最新回复
(
0
)