首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。 假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下: (
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。 假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下: (
admin
2017-11-20
48
问题
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。
假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下:
(1)初始化U={u}。以u到其他顶点的所有边为候选边。
(2)重复以下步骤n-1次,使得其他n-1个顶点被加入到U中。
从候选边中挑选权值最小的边加入到TE,设该边在V-U中的顶点是v,将v加入U中。考查顶点v,将v与V-U顶点集中的所有边作为新的候选边。
若此方法求得的T是最小生成树,请予以证明。若不能求得最小生成树,请举出反例。
选项
答案
此方法不能求得最小生成树。例如,对于图7-11a所示的带权连通无向图,按照上述方法从顶点0开始求得的结果为图7-11b所示的树,显然它不是最小生成树,正确的最小生成树如图7-11c所示。 在有些情况下,上述方法甚至无法求得最小生成树。例如对于图7-11d所示的带权连通无向图,从顶点0出发,找到顶点1(边(0,1)),从顶点1出发,找到顶点3(边(1,3)),再从顶点3出发,找到顶点0(边(3,0)),这样构成回路,就不能求得最小生成树了。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/aARi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
下列选项中,对东汉度田问题的描述中,不正确的是()
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
在第二次世界大战中的各战场中,反法西斯力量最先转入反攻的是()
第三次科技革命对社会经济结构的影响是()。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
一个在以太网中的主机试图发送一个帧,当它尝试了16次仍然失败之后,它应该()。
随机试题
我国基金会计的会计主体是基金托管人。( )
A.胃俞B.下脘、梁门C.太冲D.膈俞肝气犯胃所致的胃痛除选主穴外还可配用
Crohn病的病变特点不包括
产后宫颈外形恢复到未孕状态出现在:产后血性恶露转变为浆液性恶露多在:
下列药物用法不正确的是
平胃散的君药是理中汤的君药是
下列先天性心脏病中,哪种属于无分流型( )。
简述选题的基本要求。
按照ITU标准,传输速率为622.080Mbps的标准是()
设a=10,b=5,c=1,执行语句Printa>b>c窗体上显示的是()。
最新回复
(
0
)