**主线————线性代数：矩阵与图论**
每一张图（n个节点+m条边）都有一个对应的矩阵（*incidence matrix*），我们姑且把它记为M好了，M是一个m*n的矩阵，比如说一个图有四个节点：1、2、3、4。1与2、3、4联结；2与1、3联结；3与1、2、4联结；4与1、3联结（没法画图，脑补一下）。那么这个图的对应矩阵M就是一个5*4的矩阵，每一行表示一条边，每一列表示一个节点，-1表示从这个节点出发，1表示进入这个节点（没错这玩意还是个有向图）。很快啊，我随便标了边的方向和序号，所以说这个矩阵就应该长这样：
-1 1 0 0
0 -1 1 0
-1 0 1 0
-1 0 0 1
0 0 -1 1
好，我们看一看这个矩阵的秩，突然发现不对劲，话说这前三行好像线性相关。这说明了什么？思考两行
思考时间到。回头看一下图（本来这就是一个描述图的矩阵），你会发现这三条边形成了一个回路，绕了个圈回来了！这就很神奇了，是吧，想一下为什么。
思考时间到，第三行表示的是一条从1到3的路（可以这么理解），而第1、2两行表示的分别是从1到2的路和从2到3的路，那么加起来以后就是一条从1到3的路，而刚好又有一条从一到三的边，这两条不同的从一到三的路就形成了一条回路。
回路的问题解释清楚了以后，再继续看矩阵的秩，r（M）在这里等于3（消一下元就知道了）。那么r（M）为什么等于3呢？想一下之前讨论的回路，是不是把所有的回路都去掉就是一个线性无关的矩阵了。
是的。那么一个没有回路的图是什么？是一棵树。由此易知对于一张图，r(M)=n-1。DIM(N(A^T))=M-r。所以#nodes+#edges+#loops=1，也就是欧拉公式（欧拉：你说的是哪一个）。
对于这种M，Mx=0的意义又是什么，比如说上面这个M这里的x就是{ｃ,ｃ,ｃ,ｃ}，这种矩阵有很多实际应用，比如说这是一张电路的图，那么这个x就表示每个节点电压相等的时候各个边上的电势差等于０。然后Ｍ^T*y=0又是什么意义，因为M取了T，所以y就表示每一条边上面的电流，M^T*y=0其实就是基尔霍夫定律。因为这两个方程未知量是x、y，所以理论上来说有Ax=e和y=Ce（C是某个常量矩阵）这就是欧姆定律，如果你深度思考一下，你会发现C其实是电导率矩阵（电阻的倒数）。
最后，有一个大集合版本的方程啊A^T*C*A*x=f 至于意义嘛......其实就是前面几个方程糊到一起，嘻嘻（逃）。