n个顶点的生成树具有n-1条边，那么具有n-1条边、n个顶点的图一定存在生成树。

题目

n个顶点的生成树具有n-1条边，那么具有n-1条边、n个顶点的图一定存在生成树。

相似考题

1.图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n个顶点的生成树有n－1条边,最小代价生成树是唯一的。( )此题为判断题(对，错)。

2.有n个顶点和n－1条边的无向图一定是生成树。()此题为判断题(对，错)。

3.一棵有n个顶点的生成树有且仅有n－1条边。()此题为判断题(对，错)。

4.n个顶点的连通图的生成树有()条边。A.nB.n-1C.n+1D.不确定

更多“n个顶点的生成树具有n-1条边，那么具有n-1条边、n个顶点的图一定存在生成树。”相关问题

  • 第1题：

    n个顶点的强连通图中至少含有(14)。

    A．n-1条的向边

    B．n条有向边

    C．n(n-1)/2条有向边

    D．n(n-1)条有向边


    正确答案：B
    解析：n个顶点的强连通图中边最少的情况是，从一个顶点开始顺序连接各点，最后回到该点，它们整体上恰好构成一个圆环。此时有n条有向边。

  • 第2题：

    在具有n个顶点的完全图Kn中删去(59)边才能得到树?

    A．n(n-1)/2

    B．(n-1)×(n-2)/2

    C．n(n-2)/2

    D．n/2


    正确答案：B
    解析：n个顶点的完全图K，中共有n×(n-1)/2条边，n个顶点的树应有n-1条边，于是，删去的边有：n×(n-1)/2-(n-1)=(n-1)×(n-2)/2

  • 第3题：

    如果无向图G有n个顶点，那么G的一棵生成树有且仅有（）条边。


    正确答案:n-1

  • 第4题：

    连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。


    正确答案:错误

  • 第5题：

    具有n个顶点的有向图最多有（）条边。

    • A、N
    • B、n（n-1）
    • C、n（n+1）
    • D、n2

    正确答案:B

  • 第6题：

    在一个具有n个顶点的有向完全图中包含有（）条边

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

    正确答案:B

  • 第7题：

    如果n个顶点的图是一个环，则它有（）棵生成树。（以任意一顶点为起点，得到n-1条边）


    正确答案:n

  • 第8题：

    一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。


    正确答案:极小连通子图

  • 第9题：

    一个具有n个顶点的有向图最多有（）条边。

    • A、n×（n-1）/2
    • B、n×（n-1）
    • C、n×（n+1）/2
    • D、n2

    正确答案:B

  • 第10题：

    填空题
    一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。

    正确答案： 极小连通子图
    解析： 暂无解析

  • 第11题：

    填空题
    对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。

    正确答案： n,n-1
    解析： 暂无解析

  • 第12题：

    单选题
    关于图的生成树，下列说法不正确的是（）。
    A

    它又称为图的支撑树。

    B

    图有生成树的充要条件是该图为连通图。

    C

    图的生成树是唯一的。

    D

    顶点数为n的图的生成树有n-1条边。


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

  • 第13题：

    n个顶点的强连通图中至少含有 ( )

    A．n-1条有向边

    B．n条有向边

    C．n(n-1)/2条有向边

    D．n(n-1)条有向边


    正确答案：B

  • 第14题：

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

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

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

  • 第15题：

    关于图的生成树，下列说法不正确的是（）。

    • A、它又称为图的支撑树。
    • B、图有生成树的充要条件是该图为连通图。
    • C、图的生成树是唯一的。
    • D、顶点数为n的图的生成树有n-1条边。

    正确答案:C

  • 第16题：

    图的生成树（），n个顶点的生成树有（）条边。


    正确答案:唯一性不能确定；n-1

  • 第17题：

    一棵有N个顶点的生成树有且仅有（）条边。


    正确答案:N-1

  • 第18题：

    n个顶点的完全有向图中含有（）。

    • A、n-1条有向边
    • B、n条有向边
    • C、n（n-1）/2条有向边
    • D、n（n-1）条有向边

    正确答案:D

  • 第19题：

    由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。

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

    正确答案:B

  • 第20题：

    对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。


    正确答案:n；n-1

  • 第21题：

    判断题
    连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。
    A

    对

    B

    错


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

  • 第22题：

    单选题
    由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。
    A

     n

    B

     n-1

    C

     n+1

    D

     2×n


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

  • 第23题：

    填空题
    如果n个顶点的图是一个环，则它有（）棵生成树。（以任意一顶点为起点，得到n-1条边）

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

  • 第24题：

    填空题
    图的生成树（），n个顶点的生成树有（）条边。

    正确答案： 唯一性不能确定,n-1
    解析： 暂无解析

相关内容