MIT 线性代数导论第十二讲：图和网络

超、凢脫俗 2022-05-08 10:18 318阅读 0赞

本讲的主要内容：

*  将线性代数与实际问题（图）联系起来

首先，在之前的一节中，我们了解了图的基本概念，本讲的例子：如下  
![70][]  
在这个图中有四个结点，五条边。上面的图可以表示很多实际的问题，例如，如果上图表示电路网，带有箭头的线就表示电流以及方向。

由上面的图，我们将它的关联矩阵（Incidence Matrix）写出来：  
注意关联矩阵的4列分别表示4个结点，行分别表示5条边，其中出点标记为-1，入点标记为1.  
 A = ( − 1 1 0 0 0 − 1 1 0 − 1 0 1 0 − 1 0 0 1 0 0 − 1 1 ) A=\\begin\{pmatrix\} -1 & 1 & 0 & 0\\\\ 0 & -1 & 1 & 0\\\\ -1 & 0 & 1 & 0\\\\ -1 & 0 & 0 & 1\\\\ 0 & 0 & -1 & 1 \\end\{pmatrix\} A=⎝⎜⎜⎜⎜⎛−10−1−101−10000110−100011⎠⎟⎟⎟⎟⎞

考虑矩阵  A A A 的零空间，经过消元和回代：  
 A x = ( x 2 − x 1 x 3 − x 2 x 3 − x 1 x 4 − x 1 x 4 − x 3 ) = ( 0 0 0 0 0 ) Ax=\\begin\{pmatrix\} x\_\{2\}-x\_\{1\}\\\\ x\_\{3\}-x\_\{2\}\\\\ x\_\{3\}-x\_\{1\}\\\\ x\_\{4\}-x\_\{1\}\\\\ x\_\{4\} - x\_\{3\} \\end\{pmatrix\}=\\begin\{pmatrix\} 0\\\\ 0\\\\ 0\\\\ 0\\\\ 0 \\end\{pmatrix\} Ax=⎝⎜⎜⎜⎜⎛x2−x1x3−x2x3−x1x4−x1x4−x3⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛00000⎠⎟⎟⎟⎟⎞  
通过分析矩阵的秩： r = 3 r=3 r=3，所以  d i m N ( A ) = 1 dim\\enspace N(A)=1 dimN(A)=1 ，可以得到零空间的一组基：  
 c ( 1 1 1 1 ) c\\begin\{pmatrix\} 1\\\\ 1\\\\ 1\\\\ 1\\\\ \\end\{pmatrix\} c⎝⎜⎜⎛1111⎠⎟⎟⎞  
结合考虑实际的情况，使用这个图表示电路网，那么通过这个方程可以计算途中不同结点的电势差。

如果将矩阵转置：计算  A T y = 0 A^\{T\}y = 0 ATy=0，其中 y 1 y 2 y 3 y 4 y 5 y\_\{1\}y\_\{2\}y\_\{3\}y\_\{4\}y\_\{5\} y1y2y3y4y5均表示电流：  
 A T y = ( − y 1 − y 3 − y 4 = 0 y 1 − y 2 = 0 y 2 + y 3 − y 5 = 0 y 4 + y 5 = 0 ) = 0 A^\{T\}y= \\begin\{pmatrix\} -y\_\{1\}-y\_\{3\}-y\_\{4\} = 0\\\\ y\_\{1\}-y\_\{2\}=0\\\\ y\_\{2\}+y\_\{3\}-y\{5\}=0\\\\ y\_\{4\}+y\_\{5\} = 0 \\end\{pmatrix\}=0 ATy=⎝⎜⎜⎛−y1−y3−y4=0y1−y2=0y2\+y3−y5=0y4\+y5=0⎠⎟⎟⎞=0  
如果我们对应图考虑上面的方程，可以理解为电流的流入等于流出，也就是守恒的。

回到  A A A，我们已经知道了它的秩是3，考虑它的主列，符合要求的一个是取1、2、4列，如果我们将对应的边（第1、2、4边）在图中划出，则会发现一个结论：  
主列所对应的边，不会有回路，也就是组成了一棵树（Tree）

此外，结合之前的维数、秩的关系式：  
 d i m N ( A T ) = m − r ， r = n − 1 dim\\enspace N(A^\{T\}) = m - r，r=n-1 dimN(AT)=m−r，r=n−1  
放在图的意义中表示,也就是：  
**回路数 = 边数 - （结点数-1）**  
这个就是图论中重要的公式，欧拉公式。

以上~

[70]: /images/20220508/c2454bf2a6e14a1887400c89cc04bc05.png