niusouti.com

设,|V|=n(n>1),当且仅当(59),G=是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有通设，|V|=n(n＞1)，当且仅当(59)，G=＜V，E＞是强连通图。A．G中至少有一条路B．G中至少有一条回路C．G中有通过每个结点至少一次的路D．G中有通过每个结点至少一次的回路

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

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

A．G中至少有一条路

B．G中至少有一条回路

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

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

相似考题

1.McCabe度量法计算公式为：V(G=m-n+p，其中V（G是强连通有向图G中的环数;m是G中的弧数;n是G中的节点数;p是G中分离部分的数目）。此题为判断题(对，错)。

2.n个顶点的强连通图的边数至少有（ ）。A. n-1B. n(n-1)C. nD. n+1

3.设|V|1,D=V,E是强连通图,当且仅当()。A、D中至少有一条通路B、D中至少有一条回路C、D中有通过每个结点至少一次的通路D、D中有通过每个结点至少一次的回路

4.n个顶点的强连通图的边数至少有（ ）。A．n-1B．n（n-1）C．nD．n+1

更多“设,|V|=n(n>1),当且仅当(59),G=<V,E>是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有通 ”相关问题

  • 第1题：

    n个顶点的强连通图的边数至少有 ______.

    A．n-1

    B．n(n-1)

    C．n

    D．n+l


    正确答案：C
    解析：在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状，因而至少应有n条边。

  • 第2题：

    表达式G是不可满足的,当且仅当对所有的解释()。

    A.G为真

    B.G为假

    C.G为非永真

    D.以上都不对


    参考答案：B

  • 第3题：

    n个顶点的强连通图的邻接矩阵中至少有(34)个非零元素。

    A．n-1

    B．n

    C．2n-2

    D．2n


    正确答案：C
    解析：本题考查强连通图的概念和性质。在有向图G中，若对于V(G)中任意两个不同的顶点Vi和Vj，都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。邻接矩阵反映顶点间邻接关系，设G=(V，E)是具有n(n1)个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，并有若(i，j)或∈E，则M[i][j]=1；否则，M[i][j]=0。题目中要求邻接矩阵中非零元素至少有多少个，在做题时我们需要考虑无向图和有向图两种情况。对于无向连通图边的要求是至少为n-1，那么在其邻接矩阵中的非0元素个数就至少为2n-2。对于有向强连通图弧的要求是至少为2(n-1)，因此，在其邻接矩阵中的非0元素个数就至少为2n-2。

  • 第4题：

    设|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的说法不能成为强连通图的充要条件。

  • 第5题：

    n个顶点．的连通图至少有( )条边。

    A．n-1

    B．n

    C．n+1

    D．0


    正确答案：A
    解析：n个顶点的连通图至少有n-1条边。

  • 第6题：

    某图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如下所示。

  • 第7题：

    设有向图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′为连通图而非连通分量，图的连通分量是指无向图中的极大连通子图。

  • 第8题：

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

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

    正确答案:B

  • 第9题：

    n个顶点的强连通图的邻接矩阵中至少有（）个非零元素。

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

    正确答案:B

  • 第10题：

    n个顶点的强连通图至少有（）条边，其形状是（）。


    正确答案:n；环状

  • 第11题：

    填空题
    设G为具有N个顶点的无向连通图，则G至少有（）条边。

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

  • 第12题：

    单选题
    n个顶点的强连通图的邻接矩阵中至少有（）个非零元素。
    A

    n-1

    B

    n

    C

    2n-2

    D

    2n


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

  • 第13题：

    n个顶点的强连通图至少有( )条边。

    A、 n-1

    B、 n

    C、 2n

    D、 n(n-1)


    正确答案: A

  • 第14题：

    在一个具有n个顶点的有向图中,构成强连通图时至少有()条边。

    A.n

    B.n+1

    C.n-1

    D.n/2


    参考答案：A

  • 第15题：

    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()。

    A.G中有弧

    B.G中有一条从Vi到Vj的路径

    C.G中没有弧

    D.G中有一条从Vj到Vi的路径


    正确答案：D

  • 第16题：

    n个顶点的强连通图至少有(32)条边。

    A．n

    B．n-1

    C．n-2

    D．n+1


    正确答案：A
    解析：强连通图是指有向图，是指任何两个顶点之间都有路径存在。两个顶点要连通只要2条相反的弧，三个顶点只要3条组成环的弧。所以答案选A。

  • 第17题：

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

    A．G′为G的子图

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

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

    D．G′为G的边通分量


    正确答案：D
    解析：本题考查无向图与其生成树的关系。对于无向图而言，如果无向图G是一个连通图，在对其进行遍历时，一次可以遍历所有顶点，得到的极小连通子图是一棵生成树，树中包含了图的所有顶点，但不一定包含所有的边；如果无向图G是一个非连通图，在对其进行遍历时，得到的是森林，这个森林是由图的连通分量的生成树组成的，森林中也不一定包含图中所有的边。因此，G'不一定为G的边通分量。

  • 第18题：

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

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

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

  • 第19题：

    设某强连通图中有n个顶点，则该强连通图中至少有()条边。

    A.n+1
    B.n(n-1)
    C.n
    D.n(n+1)

    答案：C
    解析：
    强连通图是指在一个有向图中，若从节点i到节点j有路径，并且节点j到i有路径，那么为强连通图。

  • 第20题：

    设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

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

    正确答案:C

  • 第21题：

    设G为具有N个顶点的无向连通图，则G至少有（）条边。


    正确答案:N-1

  • 第22题：

    单选题
    设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
    A

    n（n-1）

    B

    n+1

    C

    n

    D

    n（n+1）


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

  • 第23题：

    单选题
    n个顶点的强连通图的边数至少有（）。
    A

    n-1

    B

    n（n-1）

    C

    n

    D

    n+1


    正确答案： A
    解析： 在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状，因而至少应有n条边。

相关内容