首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有人提出这样的一种从图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
50
问题
有人提出这样的一种从图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
学硕统考专业
相关试题推荐
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
下列关于湘军的叙述中不正确的是()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
神圣罗马帝国的解体是在第()次反法联盟之后。
唐代在广州设立管理对外商务的是()。
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
设有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。共
随机试题
潞金融资产管理公司注册资本金为_______。
重型霍乱患者治疗的关键是()
药物"七情"中,非有益配伍是
醋制延胡索是为了
建设单位管理费通常按( )的一定比例估算。
下列有关印花税的表述正确的有()。
从社会政策角度来看,人的需要有( )的特点。
公安领导工作,主要有政治领导工作、行政领导工作和业务领导工作。()
Ametaphorisapoeticdevicethatdealswithcomparison.Itcomparessimilarqualitiesoftwodissimilarobjects.Withasimple
Whenmymotherlearnedshewaspregnantwithme,myparentssatdownoneSundaymorningtoreviewtheirfinances.Turningonthe
最新回复
(
0
)