Question

有向图的邻接矩阵一定是对称的吗?

具体题目是这样的：
以下关于图及其存储结构的叙述中，正确的是：
A.无向图的邻接矩阵一定是对称的
B.有向图的邻接矩阵一定是不对称的
C.无向图采用邻接表存储更节省存储空间
D.有向图采用邻接表存储更节省存储空间
那么节省空间一说怎么看呢？

Answer 1

有向图的邻接矩阵不一定是对称的，题目答案选A。

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} [1]  。G的邻接矩阵是一个具有下列性质的n阶方阵：

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

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

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

扩展资料：

邻接矩阵特点

无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。

无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。

参考资料来源：百度百科——邻接矩阵

Answer 2

选A 无向图的邻接矩阵一定是对称的。因为如果一个点i到j有边，则aij=aji=1;所以都是对称的。但是有向图就不一定了，点i 到 j 有边，aij=1,但j到i不一定有边，则aji不一定等于1、

有向图用邻接矩阵更加节省存储空间。因为无向图的邻接矩阵是对称的，所以也就是多用了一些存储空间。

Answer 3

有向图的邻接矩阵不一定是对称的，因为它是有方向的，假如从a到b是可以通行的，但是从b到a则是逆行，为0。