首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
admin
2012-06-26
83
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(el,e2,…,em);
i=1;
while(所剩边数>=顶点数){
从图中删去ei;
若图不再连通。则恢复ei;
i=i+1;
}
请问上述方法能否求得原图的最小生成树?若该方法可行,请证明之;否则请举例说明。
选项
答案
题目中方法能求得最小生成树。证明如下: (1)从算法中while(所剩边数≥顶点数)来看,循环到边数比顶点数少1(即n一1)停止,这符合n个顶点的连通图的生成树有n一1条边的定义; (2)由于边是按权值从大到小排序,删去的边是权值大的边,结果的生成树必是最小生成树; (3)算法中“若图不再连通,则恢复ei”,含义是必须保留使图连通的边,这就保证了是生成树,否则或者是有回路,或者成了连通分量,均不再是生成树。所以,题目中方法可以求得图的最小生成树。
解析
无向连通图的生成树包含图中全部n个顶点,以及足以使图连通的n—l条边。而最小生成树则是各边权值之和最小的生成树。所以要证明题目中的方法正确,需要从以下方面证明,即:n个顶点的连通图的生成树有n一1条边;所构成的生成树的边的权值之和最小。
转载请注明原文地址:https://kaotiyun.com/show/Gyxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
蒸汽机从发明到应用经历了84年,电动机为63年,原子能利用为6年,晶体管为4年,这突出说明了()。
在巴黎和会上获利最大的两个国家是()。
明治维新中,事实上废除了封建领主土地所有制的举措是()。
导致俄国革命去和平发展可能的事件是()。
试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。
所罗门死后不久,以色列犹太王国遂分裂为北方的以色列王国和南方的犹太王国。后来,两国分别为哪两个国家所灭?()
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
著名的网络OSI七层模型是由()组织提出来的。
试用7418l和门电路实现一位余3码加法器。
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
随机试题
感染过程中,血液中最先出现的是()
自主神经系统的功能特点是
消毒的含义是
厌氧菌感染伤口换药选用
选择围堰类型时,必须根据当时当地具体条件,主要原则有()。
用经常性预算收入来偿还到期国债的本息,其实质相当于()。
配制黑火药用的原料是火硝、硫磺和木炭。火硝的质量是硫磺和木炭的3倍,硫磺占原料总量的1/10,要配制这种黑火药320千克,需要木炭多少千克?
按表中数据计算可知,1996年该省房地产业增加值为()。
ThankyouforyourinquiryofOctober1st.Wearenowsendingyouourcatalogtogetherwithsomesamplesofthematerialsyoure
【B1】【B10】
最新回复
(
0
)