首页 > 试题广场 >

对某个无向图的邻接矩阵来说，下列哪种说法是正确的( ）

[单选题]

第i行上的非零元素个数和第i列的非零元素个数一定相等

矩阵中的非零元素个数等于图中的边数

第i行上和第i列上非零元素总数等于顶点Vi的度数

矩阵中非全零行的行数等于图中的顶点数

查看答案及解析

推荐

白驹之过隙

选A。

无向图的邻接矩阵属于对称的，所以A正确。

矩阵中的一半非零元素个数等于图中的边数，所以B错误。

第i行上和第i列上非零元素总数和单个Vi顶点度数没关系。所以C错误。

顶点数和非零无关，行数为顶点数。所以D错误。

编辑于 2019-09-19 14:12:04 回复(0)

白起丶

看了下大家的解析好像对C选项说的有点不对啊，我这里说下我的看法。

在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。（所以C选项并不是没有关系哦）

发表于 2020-07-12 10:36:24 回复(0)

daisy---张

。

①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。

②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。

③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

发表于 2020-03-10 15:57:42 回复(0)

牛客169280127号

发表于 2018-12-13 23:48:44 回复(0)

wuhoo123

b 非零元素的一半等于边数

c 第i行上非零元素的个数等于vi的度

d 行数等于顶点数

发表于 2019-09-18 23:20:52 回复(0)

羊鸽哥

A正确，C错误。注意看清题目，这里考无向图。无向图: vi的度=所连边数=矩阵第i行(或者i列)中1的个数。有向图: vi的度数=入度＋出度=第i行元素之和+第i列元素之和(这里元素指1)。我看大家有说C正确的，要注意C选项对应是有向图

发表于 2022-06-11 00:45:54 回复(0)

李秋风

度不是入度+出度吗？c没错啊感觉

发表于 2020-09-04 15:25:28 回复(3)

C++coder

D中，非联通图中，会存在有顶点不与其他任何顶点相连，也就会是全零行

发表于 2022-08-08 15:09:39 回复(0)

simon_free

无向图的邻接矩阵是对称的。如果存在一条边连接顶点i和j，那么在邻接矩阵中，第i行第j列以及第j行第i列的元素都会是非零的。

因此，在邻接矩阵中，第i行上的非零元素个数与第i列的非零元素个数一定相等，它们都表示与顶点i相连的所有其他顶点的数量，也就是顶点i的度。

因为每条边都会导致两个非零元素（一个在行上，一个在列上），所以非零元素的总数总是偶数。而且，这些非零元素两两对应，形成了一对一对的边。所以，矩阵中的非零元素个数等于图中的边数的两倍。

在无向图中，如果存在一条边连接顶点i和j，那么在邻接矩阵中，第i行第j列以及第j行第i列的元素都会是非零的。因此，在邻接矩阵中，第i行上的非零元素个数与第i列的非零元素个数一定相等，它们都表示与顶点i相连的所有其他顶点的数量，也就是顶点i的度。

所以，对于一个给定的顶点Vi，其度数就是该顶点在邻接矩阵中所在行（或列）的非零元素总数。

发表于 2023-11-16 13:41:42 回复(0)

内向且正义

第i行上和第i列上非零元素总数等于顶点Vi的度数

是vi的度数是对的，可能是非零非特殊的总数（出发和开始都是自己的边）

发表于 2022-05-07 23:14:23 回复(0)

pyjac

C并没有错误，vi定点的度数 = 入度 + 出度，第i行非零元素的和为vi的出度，第i列非零元素的和为vi的入度。

发表于 2021-03-08 17:10:34 回复(0)

天尊墨宇

选A。

无向图的邻接矩阵属于对称的，所以A正确。

矩阵中的一半非零元素个数等于图中的边数，所以B错误。

第i行上和第i列上非零元素总数和单个Vi顶点度数没关系。所以C错误。

顶点数和非零无关，行数为顶点数。所以D错误。

发表于 2020-07-12 10:21:55 回复(0)

枫色

D 非零行不就是总行数吗。。有0行还能构成图吗

发表于 2020-05-11 15:13:26 回复(1)

提交观点

问题信息

图

上传者：zsw3

难度：

13条回答 118收藏 10058浏览

对某个无向图的邻接矩阵来说，下列哪种说法是正确的( ）

问题信息

热门推荐

相关试题