MIT18.06线性代数课程笔记12：使用邻接矩阵证明欧拉定理

本文主要是介绍MIT18.06线性代数课程笔记12：使用邻接矩阵证明欧拉定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

课程简介

18.06是Gilbert Strang教授在MIT开的线性代数公开课，课程视频以及相关资料请见https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/index.htm。

课程笔记

此部分是对所学线性代数知识的应用，首先通过探讨图的邻接矩阵的性质证明平面欧拉定理，然后介绍了应用基尔霍夫定律求解电势的方法。

1. 邻接矩阵的定义

图是由顶点与边组成，设顶点数为 $n$ ，边数为 $m$ ，邻接矩阵 $M$ 的形状为 $m\times n$ 。若第 $k$ 条边为由 $v_i$ 到 $v_j$ 的边，则有 $M_{ki}=-1$ 且 $M_{kj}=1$ 。

2. 邻接矩阵的性质

所谓性质，即讨论其left null space以及row space。
其left null space的定义为 $\{y|M^Ty=0\}$ ，则有其基对应于图中网孔。基底为sum(abs(y))最小的 $m-r$ 个线性无关向量。

https://baike.baidu.com/item/%E5%9F%BA%E5%B0%94%E9%9C%8D%E5%A4%AB%E5%AE%9A%E5%BE%8B/2371560?fr=aladdin
4、网孔：
（1）其内部不包含任何支路的回路。
（2）网孔一定是回路，但回路不一定是网孔。

那row space则是线性无关的边，即row space的基底组成的图不存在回路（left null space维度为0）。所以row space的维度为 $n-1$ ，因为只包含row space的基底所在边的原图子图为树，边数为 $n-1$ 。
综上 $r=n-1$ , $r(N(M^T)) = m-r = m-(n-1)$

3. 直推平面欧拉定理

直接带入left null space维度以及 $m,n$ 的物理意义可得：点数+网孔数-边数=1 （ $n+r(N(M^T))-m=1$ ）

4. 使用邻接矩阵应用基尔霍夫定律的例子

设 $u=[u_1,u_2,\cdots,u_n]^T$ 为顶点电势，有 $Mu$ 为每条边对应的电势差。进而电流为 $CMu$ ，其中 $C$ 为对角阵，因为电流是电压的常数倍。应用基尔霍夫定律 $M^TCMu=0$ ，即每个顶点的进电流和出电流相等。求解上诉等式，可得各点电势 u <script type="math/tex" id="MathJax-Element-23">u</script>。