问题 单项选择题

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

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(n≥1)个顶点的图,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。

选择题
单项选择题