2. 考研
  3. 有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下： (1)初始化U={

有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下： (1)初始化U={

admin2017-04-28  58
问题 有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：
(1)初始化U={u}。以u到其他顶点的所有边为候选边。
(2)重复以下步骤n—l次，使得其他n—1个顶点被加入到U中。从候选边中挑选权值最小的边加入到TE，设该边在V—U中的顶点是V，将V加入U中。考查顶点V，将V与V—U顶点集中的所有边作为新的候选边。若此方法求得的T是最小生成树，请予以证明。若不能求得最小生成树，请举出反例。
选项
答案此方法不能求得最小生成树。例如，对于图7—11a所示的带权连通无向图，按照上述方法从顶点0开始求得的结果为图7—11b所示的树，显然它不是最小生成树，正确的最小生成树如图7—11c所示。 [*] 在有些情况下，上述方法甚至无法求得最小生成树。例如对于图7—lld所示的带权连通无向图，从顶点0出发，找到顶点1(边(0，1))，从顶点1出发，找到顶点3(边(1，3）），再从顶点3出发，找到顶点0(边(3，0）），这样构成回路，就不能求得最小生成树了。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/oJRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)