图和网络

Graphs and Networks

本节讲述图的关联矩阵(incidence matrix):n个节点由m条边关联，通常边比节点多，m>n

我们知道，任何m-n矩阵，在 $R^m,R^n$ 下分别存在2个基础子空间，分别是$A,A^T$ 的行空间和零空间。这些空间的维数和正交性是线代的基础定理。现在我们看看图怎么解释这些基础定理。

关联矩阵的元素只能是 0,1,-1，消去后还是如此。所有主元、消去乘数都是 $\pm 1$.所以 A=LU 的2个矩阵因子的元素都是 0,1,-1,零空间矩阵也是如此！如下是第1个关联矩阵....