首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有人提出这样的一种从图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
20
问题
有人提出这样的一种从图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
学硕统考专业
相关试题推荐
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
有人说,巴黎和会是一次分赃会议,下列《凡尔赛和约》中哪一方面的内容最能体现这一性质?()。
经过多年较量,明政府认为起义军中“最强无过闯王”,这里闯王指的是()。
中华人民共和国恢复了在联合国合法席位的时间是()。
在捍卫和传播生物进化论方面做出了贡献的是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
明朝中叶,美洲高产的农作物()的传入,对改变当时人们的食品结构产生了重大影响。
加尔文教传播到法国后,其信仰者被称为()。
1870年普鲁士军队侵人巴黎,法国人民组织国民自卫军誓保卫巴黎,参加国民自卫军的大部分是()。
随机试题
阅读下文,回答问题。杨柳丰子恺因为我的画中多杨柳,就有人说我喜欢杨柳;因为有人说我喜欢杨柳,我似觉自
Hishardwork______whenhewontheprize.
2010年5月,某镇农民甲、乙、丙三人因平时关系较好,他们商量每人出资3万元创办一普通合伙企业,企业名称为温和被服加工厂。为了解决资金短缺困难,甲、乙、丙向镇信用社贷款30万元。5月底,甲、乙、丙三人签订了合伙创办温和被服加工厂的协议,并向工商行政管理机关
根据《环境影响评价技术导则—声环境》,声环境现状调查需收集评价范围内()地理地形图。
用人单位与劳动者就支付拖欠的劳动报酬达成调解协议,在协议约定期限内,如用人单位不履行,劳动者可以持调解协议书依法向()申请支付令。
下列教育家中,()提出了“泛智主义”教育思想,主张“把一切事物教给一切人”。
新课程要求老师角色怎么转变?
下列关于χ2分布的特点描述,正确的有
CD唱片的数字化音频信号其采样频率定义为44.1:kHz,主要是因为(23)。
Oldpeoplearealwayssayingthattheyoungpeoplearenot【C1】______theywere.Thesamecommentis【C2】______fromgenerationtog
最新回复
(
0
)