线性代数--MIT18.06(十二)

正文共：2716 字 39 图 预计阅读时间： 7 分钟

12. 图和网络（线性代数的应用）

12.1 课程内容：图和网络

这一讲讲解线性代数的应用，实际上也可以说是线性代数的来源吧。

在之前的课程中，列举了很多的矩阵，实际上它们都来自实际问题，而不是简简单单随便想出来的，这些矩阵都可以描述实际问题的拓扑结构，我们在处理这些实际问题时需要搞清楚它们的拓扑结构。

以应用数学中的一个例子来说明。在应用数学中我们使用图来表示这样的拓扑结构，图由节点和节点之间的联系--链接（或者叫边）构成。

考虑 4 个节点 5 条链接的情况，如上图所示。我们使用关联矩阵（Incidence Matrix）来表示这个图里的关系。 在关联矩阵中，每行为图中对应的边，列数为对应节点数，矩阵中 i 行 j 列的值代表着 i 行对应的边与节点 j 的关系。由此上图的关联矩阵可以表示为

由链接1，链接2，链接3我们可以观察到一个回路，这样的子图(subgraph)称为环(loop)

loop与线性依赖相关，例如链接1，链接2和链接3构成的环，从关联矩阵可以看到前三行的向量之间是相互关联的（第三行为前两行的和）。

如果是不存在环的图，则表示为树，实际上也即是关联矩阵中不相关的向量可以表示出来。

有了这些信息，我们就可以通过研究关联矩阵，来发现图中的信息。这就与我们之前讲解的线性代数的知识结合在了一起。

现在我们就来研究该关联矩阵所包含的信息

首先考虑它的零空间，可以发现

很容易就可以知道零空间为

那么与实际问题有什么联系？或者说实际问题的背景是什么？

观察发现，这可以表示为两个节点之间的电势差，整个图就是一个电网的表示了，而零空间实际上就表示了节点上的电势是由一个常数决定的（就是基的常数系数），电势存在差才会产生电流。（即零空间是表示网络中任何事也不发生的一个空间）

下面考虑列空间，由关联矩阵的定义我们知道，每一列就表示了一个节点，与实际相结合的情况是，我们总会令一个节点接地，由此其他节点的电势我们就可以计算得到。

再考虑左零空间，即

（这可能是应用数学里最基本的方程）。

我们来看看这个公式的含义是什么。

首先第一行

这很明显与节点1有关，即流入等于流出（in equals out）,在这个例子中，

流出，就表明流入也为0，所以它们的和为0。这也表明基尔霍夫电流定律（Kirchoff’s Current Law）是一个平衡方程（简单来说就是流入流出相等）。

再看其他几行所得到的方程，都可以得到相同的理解。现在我们来算算左零空间的基。我们知道 A 的秩为3，由此左零空间的维数为 m -r =2，因此左零空间的一组基由两个向量构成。

那么这两个向量的现实意义是什么呢？他们表示在图中的环。 我们很容易在图中发现两个环，环1由链接1，链接2，链接3构成，即

，令

为1，我们就可以根据电流的流入等于流出，得到一个向量

。 环2由链接3，链接4，链接5构成，即

,令

为1，我们就得到向量

。

当然我们也可以将图的最外圈看做一个环，也即是

, 令

为1，得到向量

。再考虑最后一个外环实际上就是两个内环的叠加（由内环得到的向量的和即为外环的向量），由此可知两个内环的向量就组成左零空间的基。

这实际上就是基尔霍夫电流定律（Kirchoff’s Current Law）成立的条件（电流流动的条件）,通过分离所有的环得到对应的基向量，就可以得到基，也就可以得到左零空间。

最后讨论下行空间，也即是

的列空间，从左零空间的基我们知道基向量就表示出了环中各边的关系，即表现出了相关性，那么当我们考虑列空间的时候，我们想要知道不相关的列是哪几列（即主元列），由左零空间的基我们知道可以为（1,2,4）或者（1,2,5），（1,3,4），（1,4,5）等等，也即是说总是要包含两个环中的边，然后我们就发现了树的形状，树的边总是不能构成环，也即列空间的不相关向量，矩阵的不相关列。

来总结一下:

即 环的个数 = 边的个数 - rank

= 边的个数 - (n - 1)

也可以写作:

节点个数 - 边的个数 + 环的个数 = 1

这就是欧拉公式，Euler’s formula，这个等式是对任意图的拓扑结构的伟大发现，它对每一个图都成立。 （这个等式有一个有趣的地方，节点为0维，边为1维，环为2维）

最后我们再总结一下，令电势差为 e，即

,电流与电势如何联系呢？由欧姆定律我们知道，电势差产生电流，即

（C为欧姆定律中的常数）, 电流表示为

这是最基础的三个等式。

那么我们可能还会增加外接电源，那么这时在

这里做修改，如果外接电流F，那么

。将等式合在一起就可以得到

(这里我们可以发现

, 这在第五讲中说明过，这是我们构造对称阵的一种方式，也同时说明了这个等式的求解是很方便的)这就是最后的平衡公式(balance equation)。

12.2 习题课

2011年图和网络习题课

图的结构如上图所示，问

1. 写出关联矩阵A
2. 求零空间和左零空间
3. 求

的迹

解答

1. 关联矩阵A就是表示各个边与各个节点之间的关系。边由节点G到H，则该边在G点由 -1 表征，在H点由 1 表征，矩阵的行数为边数，列数为节点数，即得到关联矩阵

1. 我们和课程中一样，将图考虑为一个电场。那么零空间实际上就表示图中各节点之间的电势差的和为0 （

就表示图中所有节点之间的电势差的和） 。因为此图是一个闭环图，并且没有外接的电源，所以只需要取这里的各个节点即可，即基向量为

, 零空间即为基向量的常数倍。对于左零空间，左零空间的基向量即表示图中环的情况（

就表示流经该图的所有电流的和）。图中可以发现两个子环，第一个子环表示为

，第二个子环表示为

, 因此

1. 迹是矩阵对角线元素之和，由于是由

构成而来，其迹也等于 A 中每个列向量的长度的平方和，对于图来说，实际上就是各个节点连边的数量之和。 因此很容易得到

PS：

1. 后台回复“线性代数”，“线代” 等任一关键词获取资源链接

2. 后台回复“联系“, “投稿“, “加入“ 等任一关键词联系我们