Question

对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是( )

A：n B：（n-1）*（n-1） C：n-1 D：n（n+1）/ 2

这个参考答案是D，可是我觉得是n^2
到底为什么呢？求解 啊？到底哪个对呢

Answer 1

该矩阵的大小是：n（n-1）/2

解题过程如下：

设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：

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

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

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

所以该矩阵的大小是n（n-1）/2

扩展资料

求矩阵的方法：

矩阵分解是将一个矩阵分解为比较简单的或具有某种特性的若干矩阵的和或乘积 ，矩阵的分解法一般有三角分解、谱分解、奇异值分解、满秩分解等。

谱分解是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。需要注意只有对可对角化矩阵才可以施以特征分解。

假设M是一个m×n阶矩阵，其中的元素全部属于域K，也就是实数域或复数域。其中U是m×m阶酉矩阵；Σ是m×n阶实数对角矩阵；而V*，即V的共轭转置，是n×n阶酉矩阵。这样的分解就称作M的奇异值分解。Σ对角线上的元素Σi,i即为M的奇异值。常见的做法是将奇异值由大而小排列。如此Σ便能由M唯一确定了。

Answer 2

原则上的确是n的平方，不过由于无向图的邻接矩阵是一个对称矩阵，只需要存储下三角或者上三角的元素，个数就是从1加到n，就是n（n+1）/ 2，不过题目问错了，这是压缩存储，是用一维数组存放，一般好像不叫矩阵
其实更精确地说，上面的数字个数是普通对称矩阵的，这个邻接矩阵的对角线一定为0，所以，只需要存储1 加到n-1，也就是n(n-1)/2就可以了

追问

那如图，如果是一半的话，也应该是n^2 / 2，为什么要n(n+1) / 2 呢？

追答

所谓对称矩阵就是aij = aji，这样必须包括对角线在内，第1行1个，第2行两个，.....，第n行n个，加起来不就是n(n+1)/2，话说回来，如果是9x9矩阵，n^2 = 81，除2为40.5，如何存储这0.5个元素？