设有一个无向图G=(V，E)和G′=(V′,E′)，如果G′为G的生成树，则下面不正确的说法是(40)。A．G′为G的子图B．G′为G的极小连通子图且V′=VC．G′为G的一个无环子图D．G′为G的边通分量

题目

设有一个无向图G=(V，E)和G′=(V′,E′)，如果G′为G的生成树，则下面不正确的说法是(40)。

A．G′为G的子图

B．G′为G的极小连通子图且V′=V

C．G′为G的一个无环子图

D．G′为G的边通分量

相似考题

1.设V'和E'分别为无向连通图G的点割集和边割集，下面的说法中正确的是Ⅰ．G-E'的连通分支数p(G-E')=2。Ⅱ．G-V'的连通分支数p(G-V')一定等于G-E'的连通分支数p(G-E')。Ⅲ．G-V'的连通分支数p(G-V')≥2。A．Ⅰ和ⅡB．Ⅰ和ⅢC．ⅡD．没有

2.有向图G=(V，E)，其中V={a，b，c，d}，E={a，ba，d，b，c，c，d}，则图G为强连通图。()

3.设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1ÍV2,E1ÍE2则称()。A、G1是G2的子图B、G1是G2的连通分量

4.设G是n个顶点的无向简单图,则下列说法不正确的是()A、若G是树，则其边数等于n-1B、若G是欧拉图，则G中必有割边C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路

更多“设有一个无向图G=(V,E)和G′=(V′,E′),如果G′为G的生成树,则下面不正确的说法是(40)。A.G′为G的子图 ”相关问题

  • 第1题：

    设|V|=n(n>1),当且仅当______,G=是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有

    设|V|=n(n＞1)，当且仅当______，G=＜V，E＞是强连通图。

    A．G中至少有一条路

    B．G中至少有一条回路

    C．G中有通过每个节点至少一次的路

    D．G中有通过每个节点至少一次的回路

    A．

    B．

    C．

    D．


    正确答案：D
    解析：在简单有向图G中，任何一对节点间两者之间是相互可达的，则称这个图是强连通的。设|V|=n(n＞1)，当且仅当G中有通过每个节点至少一次的回路，G=V，E＞是强连通图。
      对于选项C，例如图“A→B”，即只有A到达B，有一次路，但是该图不是强连通的。因此选项C的说法不能成为强连通图的充要条件。

  • 第2题：

    某图G的邻接表如下所示。以下关于图G的叙述中，正确的是( )。

    A.G是强连通图
    B.G是有7条弧的有向图
    C.G是完全图
    D.G是有7条边的无向图

    答案：B
    解析：
    本题考查数据结构基础知识。
    顶点A、B、C、D、E的编号分别为1、2、3、4、5。如果为无向图，则每条边在邻接表中会表示两次，因此表结点的数目应为偶数。题中的邻接表中有7个表结点，显然是有向图。
    从顶点A的邻接表中可知，编号为2和3的顶点为A的邻接顶点，即存在弧＜A，B＞和＜A,C＞。
    从顶点B的邻接表中可知，编号为3、4和5的顶点为B的邻接顶点，即存在弧＜B,C＞、＜B,D＞和＜B,E＞。
    从顶点C的邻接表中可知，编号为4的顶点为C的邻接顶点，即存在弧＜C,D＞。
    从顶点D的邻接表中可知，该顶点没有邻接顶点。
    从顶点E的邻接表中可知，编号为1的顶点为E的邻接顶点，即存在弧＜E,A＞。
    图G如下所示。

  • 第3题：

    设有向图G=(V，E)和G′-(V′，E′).如(G′)是G生成树，下面说法中不正确的是()

    A.G′为G的连通分量
    B.G′为G的无环子图
    C.G′为G的子图
    D.G′为G的极小连通子图且V′=V

    答案：A
    解析：
    B项、D项都是生成树的特点，而A项为概念错误：G′为连通图而非连通分量，图的连通分量是指无向图中的极大连通子图。

  • 第4题：

    以下说法不正确的是（）。

    A连通图G一定存在生成树

    B连通图G的生成树中一定包含G的所有顶点

    C连通图G的生成树中不一定包含G的所有边

    D连通图G的生成树可以是不连通的


    D
    略

  • 第5题：

    在公式V（G）=E–N+2中：E为程序图G中边的总数；N为程序图中结点的总数。V（G）又称为图G的环形（）。


    正确答案:复杂度

  • 第6题：

    在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）


    正确答案:正确

  • 第7题：

    设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1V2，E1E2则称（）。

    • A、G1是G2的子图
    • B、G2是G1的子图
    • C、G1是G2的连通分量
    • D、G2是G1的连通分量

    正确答案:A

  • 第8题：

    对于一个图G，若边集合E（G）为无向边的集合，则称该图为（）。


    正确答案:无向图

  • 第9题：

    以下有关联通图的说法不正确的是（）。

    • A、连通图G一定存在生成树
    • B、连通图G的生成树中一定包含G的所有顶点
    • C、连通图G的生成制中不一定包含G的所有边
    • D、连通图G的生成树可以是不连同的

    正确答案:D

  • 第10题：

    单选题
    设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。
    A

    G’为G的子图

    B

    G’为G的连通分量

    C

    G’为G的极小连通子图且V=V’

    D

    G’是G的一个无环子图


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

  • 第11题：

    单选题
    以下有关联通图的说法不正确的是（）。
    A

    连通图G一定存在生成树

    B

    连通图G的生成树中一定包含G的所有顶点

    C

    连通图G的生成制中不一定包含G的所有边

    D

    连通图G的生成树可以是不连同的


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

  • 第12题：

    单选题
    设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1V2，E1E2则称（）。
    A

    G1是G2的子图

    B

    G2是G1的子图

    C

    G1是G2的连通分量

    D

    G2是G1的连通分量


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

  • 第13题：

    下列命题正确的是(58)。

    A．G为n阶无向连通图，如果G的边数m≥n-1，则G中必有圈

    B．二部图的顶点个数一定是偶数

    C．若无向图C的任何两个不相同的顶点均相邻，则G为哈密尔顿图

    D．3-正则图的顶点个数可以是奇数，也可以是偶数


    正确答案：C
    解析：n阶无向连通图至少有n-1条边，但n阶无向连通图不一定有圈，所以A错误。二部图顶点个数也可以为奇数，可知D错误。由握手定理可知，n阶k-正则图中，边数m=kn/2，因而当k为奇数时，n必为偶数。所以D错误。所以选C。

  • 第14题：

    设无向图G=(V，E)和G′=(V′，E′)，如果G′是G的生成树，则下面的说法中错误的是()。

    A.G′为G的极小连通子图且V=V′
    B.G′是G的一个无环子图
    C.G′为G的子图
    D.G′为G的连通分量

    答案：D
    解析：
    连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。

  • 第15题：

    图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是（请作答此空）。对G进行广度优先遍历（从v0开始），可能的遍历序列为（ ）。


    A.无向图
    B.有向图
    C.完全图
    D.强连通图

    答案：B
    解析：

  • 第16题：

    设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。

    • A、G’为G的子图
    • B、G’为G的连通分量
    • C、G’为G的极小连通子图且V=V’
    • D、G’是G的一个无环子图

    正确答案:B

  • 第17题：

    互在任一图G中，当点集V确定后，树图是G中边数最少的连通图。


    正确答案:正确

  • 第18题：

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


    正确答案:错误

  • 第19题：

    图G的生成树是该图的一个极小连通子图


    正确答案:错误

  • 第20题：

    对于一个图G，若边集E（G）为无向边的集合，则该图为（）。


    正确答案:无向图

  • 第21题：

    填空题
    在公式V（G）=E–N+2中：E为程序图G中边的总数；N为程序图中结点的总数。V（G）又称为图G的环形（）。

    正确答案： 复杂度
    解析： 暂无解析

  • 第22题：

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

    对

    B

    错


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

  • 第23题：

    单选题
    以下说法不正确的是（）。
    A

    连通图G一定存在生成树

    B

    连通图G的生成树中一定包含G的所有顶点

    C

    连通图G的生成树中不一定包含G的所有边

    D

    连通图G的生成树可以是不连通的


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

相关内容