设,|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=＜V，E＞是强连通图。
A．G中至少有一条路
B．G中至少有一条回路
C．G中有通过每个结点至少一次的路
D．G中有通过每个结点至少一次的回路
相似考题
更多“设,|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=设|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个顶点的强连通图的邻接矩阵中至少有（）个非零元素。An-1
Bn
C2n-2
D2n
正确答案： 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个顶点，则该强连通图中至少有（）条边。An（n-1）
Bn+1
Cn
Dn（n+1）
正确答案： D解析： 暂无解析 -
第23题：
单选题n个顶点的强连通图的边数至少有（）。An-1
Bn（n-1）
Cn
Dn+1
正确答案： A解析： 在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状，因而至少应有n条边。