离散数学 - 图论(3)-图的矩阵表示

图论(3)-图的矩阵表示

• 设G=是有向图, 其中V={$v_1 ,v_2 ,…,v_n$v1​,v2​,…,vn​}, 并假定各结点已经有了从$v_1$v1​到$v_n的次序。定义一个n×n的矩阵**A**, 其中各元素$vn​的次序。定义一个n×n的矩阵∗∗A∗∗,其中各元素a_{ij}$为
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-j8p9r3lX-1597284496545)(en-resource://database/474:1)]

• 图的表示矩阵的转置表示各边反向后得到的图

• $AA^T$AAT的元素的意义:
  从结点$v_i$vi​和$v_j$vj​两者引出的边, 如果能共同终止于 一些结点, 则这些终止结点的数目就是$b_{ij}$bij​的值; 特别, i=j时, 对角线上的元素bii就是结点vi的引出次数。

• $A^TA$ATA的元素的意义:
  从一些结点引出的边,如果同时终止于$v_i$vi​和$v_j$vj​, 则这样的结点数目就是$b_{ij}$bij​的值。特别,对角线上元素的值是 各结点的引入次数。

• $A^n$An的元素的意义:
  $A^n$An的元素$a^{(n)}_{ij}$aij(n)​ 是从$v_i$vi​到$v_j$vj​的长度为n的不同路径的数目

• $B_r =A+A^2+A^3+…+A^r$Br​=A+A2+A3+…+Ar的元素 $b_{ij}$bij​ 的意义。

• 基本路径长度不超过n-1， 基本回路长度不超过n，因此仅需 考察,
  $B_{n-1} =A+A^2+A^3+…+A^{n-1}$Bn−1​=A+A2+A3+…+An−1
  或
  $B_{n} =A+A^2+A^3+…+A^{n}$Bn​=A+A2+A3+…+An
  

• 利用矩阵判断图的连通性的方法:

  1. 无向连通图：可达性矩阵P中除主对角线外全为1，对角线上的元素可能为1也可能为0；
  2. 强连通图：可达性矩阵P中除主对角线外全为1，对角线 上的元素可能为1也可能为0；
  3. 单向连通图：令$P'=P \vee P_T$P′=P∨PT​ , 则P’除主对角线外全为1, 对角 线上的元素可能为1也可能为0；
  4. 弱连通图：若图的邻接矩阵为A, 令$A'=A\vee A_T$A′=A∨AT​ , 则A’对应的无向图的可达性矩阵除对角线外全为1。