正文共:2716 字 39 图 预计阅读时间: 7 分钟
前文推送
12. 图和网络(线性代数的应用)
这一讲讲解线性代数的应用,实际上也可以说是线性代数的来源吧。
在之前的课程中,列举了很多的矩阵,实际上它们都来自实际问题,而不是简简单单随便想出来的,这些矩阵都可以描述实际问题的拓扑结构,我们在处理这些实际问题时需要搞清楚它们的拓扑结构。
以应用数学中的一个例子来说明。在应用数学中我们使用图来表示这样的拓扑结构,图由节点和节点之间的联系--链接(或者叫边)构成。
考虑 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)。
2011年图和网络习题课
图的结构如上图所示,问
的迹
解答
就表示图中所有节点之间的电势差的和) 。因为此图是一个闭环图,并且没有外接的电源,所以只需要取这里的各个节点即可,即基向量为
, 零空间即为基向量的常数倍。对于左零空间,左零空间的基向量即表示图中环的情况(
就表示流经该图的所有电流的和)。图中可以发现两个子环,第一个子环表示为
,第二个子环表示为
, 因此
构成而来,其迹也等于 A 中每个列向量的长度的平方和,对于图来说,实际上就是各个节点连边的数量之和。 因此很容易得到