问题
单项选择题
有一邻接矩阵
如果是有向图,则该图共有 (42) 条弧;如果是无向图,则该图共有 (43) 条边。
答案
参考答案:C
解析:试题42~43
[分析]:
本题考查有向图与无向图的邻接矩阵存储结构。
邻接矩阵反映顶点间邻接关系,设G=(V,E)是具有n(n≥1)个顶点的图,G的邻接矩阵M是一个n行n列的矩阵,并有若(i,j)或∈E,则M[i][j]=1;否则,M[i][j]=0。
由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,有向图的邻接矩阵不一定对称。对于无向图,其邻接矩阵第i行元素的和即为顶点i的度。对于有向图,其邻接矩阵的第i行元素之和为顶点i的出度,而邻接矩阵的第j列元素之和为顶点j的入度。
由邻接矩阵A可知,各顶点的出度和是4,如果是有向图,每条弧对应一个出度和一个入度,因此,图中有4条弧。如果是无向图,每条边对应两个度,因此,图中只有两条边。