首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(el,e2,…,em); i=1; while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通。则恢复ei; i=
admin
2012-06-26
40
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
下列对于两次世界大战之间的国际关系体系的描述,正确的一组是()①原有的四大帝国纷纷解体②中欧和东南欧已经出现了许多民族独立国家③欧洲的两侧出现了崛起的美国和社会主义的苏维埃俄国④远东出现了恶性发展的日本和独立的印度民族主义国家
下列关于中共十一大的叙述中错误的是()。
以下关于玛雅文明叙述,不正确的是()。
试析淝水之战前后南北政权的特点和变化。
列宁在()中系统地阐明了马克思主义的国家学说。
下列关于戈尔巴乔夫上台以后发生的事件,按时间先后顺序排列正确的是()。①苏联进行政治改革②苏联进行经济改革③八一九事件④苏联解体
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
设有A,B,C,D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.28.112,B主机的IP地址是192.155.28.120,C主机的IP地址是192.155.28.135,D主机的IP地址是192.155.28.202。共
某字长为8bit的计算机中,x和y为无符号整数,已知x=68,y=80,x和y分别存放在寄存器A和B中。请回答下列问题(要求最终用十六进制表示二进制序列)。无符号整数加/减运算时,加法器最高位进位Cn的含义是什么?它与进/借位标志CF的关系是什么?
随机试题
PowerPoint2010视图有哪些?如何切换?
关于肺泡表面活性物质,下列说法正确的是:()
某药存放于库房,由于保管不慎,被雨淋湿,发霉变质。药库负责人为降低损失,将此批药品降价销售。该负责人行为违反了药品管理法,此批药品不可销售,属于
马来酸依那普利可用于
我国现行房地产经纪行业管理中,通过()的建设,可以提升房地产经纪人的职业道德水平和专业水平能力,塑造良好的职业形象,提高行业的社会公信力。
饰面板(砖)工程的质量验收时,需对所用材料进行性能指标复验的有()。
某社区社会工作者在“三八妇女节”开展了面向社区妇女的专场招聘会,有380名妇女赶赴招聘会现场,其中203名妇女在当天与企业达成了就业意向。从促进社会就业来看,社会工作者的工作属于()。
【2015年河南驻马店.多选】下列属于情绪外部表现的是()。
国民生产总值和国内生产总值的关系是()。
ARegularEuropeanbusinesstravellersviewtravellingoncommercialairlinesasinefficientandinconvenient.Mostlyitisnot
最新回复
(
0
)