2. 考研
  3. 有人提出这样的一种从图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的步骤如下： (

admin2017-11-20  26
问题 有人提出这样的一种从图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://jikaoti.com/ti/UtfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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