图的邻接矩阵的若干性质论文

问：邻接矩阵的性质是什么？

1. 答：（1）图中各顶点确定后，图的邻接矩阵能唯一确定。
   （2）无向图和无向网的邻接矩阵沿主对角线对称，且主对角线上元素为0；有向图散丛和有向网的邻接矩阵不一定对称。
   （2）无向图邻接矩阵的第i行（或第i列）的非零元素的个数即为第i个顶点的度。
   （4）有向图邻接矩阵的第i行的非零元素的个数即为第i个顶点的出度，第i列的非零元素的个数即为第i个顶点的信肢入度，第i个顶点的度等于第i行与第i列非零元素个数之和。
   （5）无向图中边数等于邻接矩阵中非零元素个数之和的一半，有向图的弧数等于邻接矩阵中非零元素个数之和。
   （6）图或滑掘世网的邻接矩阵，需要一个具有n个元素的一维数组和一个具有n2个元素的二维数组存储，因此，其空间复杂度是0（n2）。

问：邻接矩阵特性的问题

1. 答：I就是n阶单位矩阵（对角元为1，非对角元全为0），有的书上写成E，有的写成I。
   (I-A)(I+A+A^2+A^3+...)
   =(I+A+A^2+A^3+...)-A(I+A+A^2+A^3+...)
   =(I+A+A^2+A^3+...)-(A+A^2+A^3+A^4+...)
   =I，
   所以(I-A)^(-1)=I+A+A^2+A^3+...。
   由邻接矩阵的定义，A中第ij个元素表示顶点i到顶点j的长度为1的路径数目，A^2中第ij个元素没郑表示顶点i到顶罩察雀点j的长度为2的路径数目，……。所以右边和式中第ij个元素表示顶点i到顶点j的所有路径数目。I-A可逆当且仅当右边和式收敛，当且仅当A幂零（即物早对充分大的n有A^n=0），当且仅当G中没有有向圈

问：图的邻接矩阵表示

1. 答：为对称矩阵。根据矩阵性质可知原因：邻接矩阵（adjacencymatrix）：是表示顶点之间相邻关系的矩阵。设g=(v,e)是一个图，其中v={v1,v2,…,vn}。g的邻接哪衫矩阵是一个具有下列性质的n阶方阵：对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零。无向图的邻接矩阵首带一定是对称的，而有向图的邻接者缓芦矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2++(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
2. 答：邻接矩阵根据有向迅判图或者无向氏判图亩核改的边的连接就可以设定，横纵坐标都是节点，有连接就为1，无连接就为0，无向图由于连接是双向的，所以是对称的。