带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

题目

带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

相似考题

1.如下所示是一个带权连通无向图，其最小生成树各边权的总和为A． 24B．25C．26D．27

2.带权的连通无向图的最小(代价)生成树必是唯一的。()

3.连通图的各边权值均不相同，则该图的最小生成树是唯一的。()

4.一棵哈夫曼树的带权(外部)路径长度等于其中所有分支结点的权值之和。()

更多“带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。”相关问题

  • 第1题：

    任何一个带权的无向连通图的最小生成树()。

    A.只有一棵

    B.有一棵或多棵

    C.一定有多棵

    D.n+2


    正确答案：B

  • 第2题：

    以下说法中正确的是(49)。

    A．带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和

    B．从源点到终点的最短路径是惟一的

    C．任意一个AOV网不一定存在拓扑序列

    D．任意一个AOE网中的关键路径是惟一的


    正确答案：C
    解析：带权连通图的某最小生成树的权值之和不一定小于其他生成树的权值之和；对于一个图而言，从源点到终点的最短路径也不一定是惟一的；任意一个AOE网中的关键路径也不一定惟一，因此，只有说法C正确。

  • 第3题：

    下面有关图的相关概念说法不正确的是【】

    A．有e条边的无向图，在邻接表中有e个结点

    B．有向图的邻接矩阵是对称的

    C．任何无向图都存在生成树

    D．不同的求最小生成树的方法最后得到的生成树的权值之和是相等的


    正确答案：ABC

  • 第4题：

    在图G点最小生成树G1中，可能会有某条边的权值超过未选边的权值。()


    答案：对
    解析：
    最小生成树其实是最小权重生成树的简称，只保证了所以权值之和最小，不好找每条路径都有最小权重。

  • 第5题：

    对于一个带权连通图，在什么情况下，利用普里姆（Prim）算法与利用克鲁斯卡尔（Kruskal）算法可能生成不同的最小生成树？


    正确答案:当图中出现权值相同的边时，利用普里姆(Prim)算法与利用克鲁斯卡尔(Kruskal)算法可能生成不同的最小生成树。

  • 第6题：

    n个顶点的带权无向连通图的最小生成树包含（）个顶点。

    • A、n-1
    • B、n
    • C、n/2
    • D、n+1

    正确答案:B

  • 第7题：

    最小生成树指的是（）。

    • A、由连通网所得到的边数最少的生成树
    • B、由连通网所得到的顶点数相对较少的生成树
    • C、连通网中所有生成树中权值之和为最小的生成树
    • D、连通网的极小连通子图

    正确答案:C

  • 第8题：

    任何带权的无向图都存在最小（代价）生成树。


    正确答案:错误

  • 第9题：

    单选题
    最小生成树指的是（）。
    A

    由连通网所得到的边数最少的生成树

    B

    由连通网所得到的顶点数相对较少的生成树

    C

    连通网中所有生成树中权值之和为最小的生成树

    D

    连通网的极小连通子图


    正确答案： D
    解析： 暂无解析

  • 第10题：

    问答题
    对于一个带权连通图，在什么情况下，利用普里姆（Prim）算法与利用克鲁斯卡尔（Kruskal）算法可能生成不同的最小生成树？

    正确答案： 当图中出现权值相同的边时，利用普里姆(Prim)算法与利用克鲁斯卡尔(Kruskal)算法可能生成不同的最小生成树。
    解析： 暂无解析

  • 第11题：

    判断题
    任何带权的无向图都存在最小（代价）生成树。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第12题：

    单选题
    n个顶点的带权无向连通图的最小生成树包含（）个顶点。
    A

    n-1

    B

    n

    C

    n/2

    D

    n+1


    正确答案： B
    解析： 暂无解析

  • 第13题：

    哈夫曼树的带权路径长度WPL等于______。

    A．除根以外的所有节点的权植之和

    B．所有节点权值之和

    C．各叶子节点的带权路径长度之和

    D．根节点的值


    正确答案：C
    解析：Huffman树又称为最优树，是一类带权路径长度最短的树。
      节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和，记为，其中n为带权叶子节点数目，为叶子节点的权值，lk为叶予节点到根的路径长度。

  • 第14题：

    带权无向图的最小生成树是唯一的。

    此题为判断题(对，错)。


    正确答案：×

  • 第15题：

    如下所示是一个带权连通无向图，其最小生成树各边权的总和为

    A．24

    B．25

    C．26

    D．27


    正确答案：C

  • 第16题：

    对于含有n个顶点的带权连通图，它的最小生成树是指()。

    A.图中任意一个由n-l条权值最小的边构成的子图
    B.图中任意一个由n-1条权值之和最小的边构成的子图
    C.图中任意一个由n-1条权值之和最小的边构成的连通子图
    D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图

    答案：D
    解析：
    一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点，但只有构成一棵树的(n-1)条边。如果小于(n-1)条边，则是非连通图；如果多于(n-1)条边，则一定有回路，因为这条边使得它依附的那两个顶点之间有了第二条路径。但是，有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。总之，含有n个顶点的带权连通图，它的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。

  • 第17题：

    若一个连通图中每个边上的权值均不同，则得到的最小生成树是（）（唯一/不唯一）的。


    正确答案:唯一

  • 第18题：

    带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。


    正确答案:正确

  • 第19题：

    一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？


    正确答案: 一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。

  • 第20题：

    若连通网络上各边的权值均不相同，则该图的最小生成树有（）棵。


    正确答案:1

  • 第21题：

    问答题
    一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？

    正确答案： 一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
    解析： 暂无解析

  • 第22题：

    填空题
    若连通网络上各边的权值均不相同，则该图的最小生成树有（）棵。

    正确答案： 1
    解析： 暂无解析

  • 第23题：

    判断题
    带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第24题：

    填空题
    若一个连通图中每个边上的权值均不同，则得到的最小生成树是（）（唯一/不唯一）的。

    正确答案： 唯一
    解析： 暂无解析

相关内容