养生 装修 购物 美食 感冒 便秘 营销 加盟 小吃 火锅 管理 创业 搭配 减肥 培训 旅游

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

时间:2024-11-15 02:17:42

有向图的邻接矩阵不一邈赕瑟遂定是对称的,题目答案选A。

邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。设G=(V荑樊综鲶,E)是一个图,其中V={v1,v2,…,vn}[1]。G的邻接矩阵是一个具有下列性质的n阶方阵:

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

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

用邻接矩阵法表示图共需要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列非零元素个数之和。用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。

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

© 一点知识