【MIT-18.06-线性代数】第十二讲：图和网络

第十二讲 图和网络

1 关联矩阵

一个图包含结点和边。

该图一共有4个结点，所以；有5条边，所以。

给每条边指定方向，如下：

可以将这考虑为电流，与参考方向相同为正，否则为负。在本讲中，将使用电势、电势差、电流之类的词汇，换言之，将图看做一个电路网络。

构造一个矩阵解释这个图的含义，称之为关联矩阵，矩阵的一行表示图的一条边，矩阵的一个列表示图的一个结点。第一条边从结点 1 指向结点 2，所以第一行为，第二条边从结点 2 指向结点 3，所以第二行为，以此类推，可以得到矩阵。

图中边1、2、3构成了一个子图，他们是一个回路，对于一个图，回路的位置和数量至关重要。观察矩阵的前三行，对应边1、2、3。他们是线性相关的，说明“回路”对应“相关”。与回路对应的行是线性相关的。

可以看到关联矩阵包含许多的 0，每行只有两个非零的数，非零数的个数一共是个。从实际问题得到图以及关联矩阵，关联矩阵源于问题，描述了问题的拓扑结构。

2 矩阵的零空间

矩阵的零空间是什么？换句话说矩阵的各列是否线性相关。

我们可以解。

注意矩阵A的实际意义，可以通过算出每条边上的差值，即结点间的电势差。将看做各结点的电势，将与它相乘，得到、等五个量是各边上的电势差。电势差什么时候为 0，除了各结点电势为 0，各结点电势相等时各边电势差也是0。所以的零空间是。

A的零空间的维数为 1，这个零空间有什么物理意义吗？表明结点电势都是由一个常数决定，电势差是产生电流的原因。

3 矩阵的零空间

方程。首先可以知道。

下面讨论这个方程的实际意义。

将上述得到的、等各边上的电势差左乘一个矩阵，得到各边上的电流。 这符合欧姆定律：边上的电流值是电势差的倍数，这个数值是电导，电阻的倒数。

令，这就是基尔霍夫定律。

第一个方程为：

从图中可以看出，该方程表示从结点1流入流出的电流总和为0。

第二个方程是关于结点2的······

求解，有两个特解，假设，则。

令，可得。可以得到两个特解分别为：。第一个基向量取得是回路1内的电流，第二个基向量取得是回路2内的电流。

4 矩阵的行空间

矩阵的行空间秩为3，有三行是线性无关的，第一行、第二行、第四行线性无关，对应边1、3、4，它们加上四个节点构成一个子图，如图所示：

子图没有回路，线性无关等价于没有回路。相关性来自于回路。

没有回路的图，表明关联矩阵的各行线性无关，叫做“树”。

5 欧拉公式

维度公式：

其中对应回路数量，对应边的数量，对应结点数量减一：。对于树，其各行线性无关，边的数目为，所以矩阵的秩为。

所以有：

整理可得：

这就是欧拉公式。