n个顶点的强连通图的邻接矩阵中至少有(34)个非零元素。A．n-1B．nC．2n-2D．2n

题目

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

A．n-1

B．n

C．2n-2

D．2n

相似考题

1.n个顶点的连通图用邻接距阵表示时,该距阵至少有()个非零元素。A.nB、2(n-1)C、n/2D、n2

2.下列叙述中正确的是（ ）。A．连通分量是无向图中的极小连通子图 B．生成树是连通图的一个极大连通子图 C．若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧 D．若一个含有n个顶点的无向图是连通图，则该图中至少有n条边

3.n个顶点的强连通图至少有(32)条边。A．nB．n-1C．n-2D．n+1

4.n个顶点的强连通图至少有( )条边。A、 n-1B、 nC、 2nD、 n(n-1)

参考答案和解析
正确答案：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。
更多“n个顶点的强连通图的邻接矩阵中至少有(34)个非零元素。A.n－1B.nC.2n－2D.2n ”相关问题

  • 第1题：

    设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于I/O分别表示顶点i与顶点j之间有/无边），则该矩阵中的非零元素数目为（ ）。

    A.N
    B.E
    C.2E
    D.N+E

    答案：C
    解析：
    本题考查数据结构的基础知识。无向图的邻接矩阵是一个对称矩阵，每条边会表示两次，因此矩阵中的非零元素数目为2E。

  • 第2题：

    n个顶点的强连通图至少有（）条边。

    A．n

    B．n+1

    C．n-1

    D．n*(n-1)


    n

  • 第3题：

    n个顶点的连通图用邻接距阵表示时，该矩阵至少有（）个非零元素。

    A．n

    B．2(n-1)

    C．n/2

    D．n*n


    C

  • 第4题：

    如果n（n＞2）个顶点的有向图有二个强连通分量，则至少有n-1条弧。


    正确

  • 第5题：

    3、有10个顶点的无向连通图，其邻接矩阵中至少有______个1。


    正确

相关内容