图和网络¶

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

dg = nx.DiGraph()
dg.add_edges_from([(1,2), (2,3), (1,3), (1,4), (3,4)])
edge_labels = {(1, 2): 1, (1, 3): 3, (1, 4): 4, (2, 3): 2, (3, 4): 5}

pos = nx.spring_layout(dg)
nx.draw_networkx_edge_labels(dg,pos,edge_labels=edge_labels, font_size=16)
nx.draw_networkx_labels(dg, pos, font_size=20, font_color='w')
nx.draw(dg, pos, node_size=1500, node_color="gray")

该图由4个节点与5条边组成，

我们可以建立5 \times 4矩阵
$
A=
\begin{bmatrix}
-1 & 1 & 0 & 0 \
0 & -1 & 1 & 0 \
-1 & 0 & 1 & 0 \
-1 & 0 & 0 & 1 \
0 & 0 & -1 & 1 \
\end{bmatrix}
$

观察前三行，易看出这三个行向量线性相关，也就是这三个向量可以形成回路（loop）。

现在，解Ax=0：
$
Ax=
\begin{bmatrix}
-1 & 1 & 0 & 0 \
0 & -1 & 1 & 0 \
-1 & 0 & 1 & 0 \
-1 & 0 & 0 & 1 \
0 & 0 & -1 & 1 \
\end{bmatrix}
\begin{bmatrix}
x_1\x_2\x_3\x_4\
\end{bmatrix}
$。

展开得到：
\begin{bmatrix}x_2-x_1 \x_3-x_2 \x_3-x_1 \x_4-x_1 \x_4-x_3 \ \end{bmatrix}=\begin{bmatrix}0\0\0\0\0\ \end{bmatrix}

引入矩阵的实际意义：将x=\begin{bmatrix}x_1 & x_2 & x_3 & x_4\end{bmatrix}设为各节点电势（Potential at the Nodes）。

则式子中的诸如x_2-x_1的元素，可以看做该边上的电势差（Potential Differences）。

容易看出其中一个解x=\begin{bmatrix}1\1\1\1\end{bmatrix}，即等电势情况，此时电势差为0。

化简A易得rank(A)=3，所以其零空间维数应为n-r=4-3=1，即\begin{bmatrix}1\1\1\1\end{bmatrix}就是其零空间的一组基。

其零空间的物理意义为，当电位相等时，不存在电势差，图中无电流。

当我们把图中节点4接地后，节点4上的电势为0，此时的
$
A=
\begin{bmatrix}
-1 & 1 & 0 \
0 & -1 & 1 \
-1 & 0 & 1 \
-1 & 0 & 0 \
0 & 0 & -1 \
\end{bmatrix}
，各列线性无关，rank(A)=3$。

现在看看A^Ty=0（这是应用数学里最常用的式子）：

A^Ty=0=\begin{bmatrix}-1 & 0 & -1 & -1 & 0 \1 & -1 & 0 & 0 & 0 \0 & 1 & 1 & 0 & -1 \0 & 0 & 0 & 1 & 1 \ \end{bmatrix}\begin{bmatrix}y_1\y_2\y_3\y_4\y_5\end{bmatrix}=\begin{bmatrix}0\0\0\0\end{bmatrix}，对于转置矩阵有dim N(A^T)=m-r=5-3=2。

接着说上文提到的的电势差，矩阵C将电势差与电流联系起来，电流与电势差的关系服从欧姆定律：边上的电流值是电势差的倍数，这个倍数就是边的电导（conductance）即电阻（resistance）的倒数。

$
电势差
\xrightarrow[欧姆定律]{矩阵C}
各边上的电流y_1, y_2, y_3, y_4, y_5
，而A^Ty=0$的另一个名字叫做“基尔霍夫电流定律”（Kirchoff's Law, 简称KCL）。

再把图拿下来观察：

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

dg = nx.DiGraph()
dg.add_edges_from([(1,2), (2,3), (1,3), (1,4), (3,4)])
edge_labels = {(1, 2): 1, (1, 3): 3, (1, 4): 4, (2, 3): 2, (3, 4): 5}

pos = nx.spring_layout(dg)
nx.draw_networkx_edge_labels(dg,pos,edge_labels=edge_labels, font_size=16)
nx.draw_networkx_labels(dg, pos, font_size=20, font_color='w')
nx.draw(dg, pos, node_size=1500, node_color="gray")

将A^Ty=0中的方程列出来：
$
\left{
\begin{aligned}
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{aligned}
\right.
$

对比看A^Ty=0的第一个方程，-y_1-y_3-y_4=0，可以看出这个方程是关于节点1上的电流的，方程指出节点1上的电流和为零，基尔霍夫定律是一个平衡方程、守恒定律，它说明了流入等于流出，电荷不会在节点上累积。

对于A^T，有上文得出其零空间的维数是2，则零空间的基应该有两个向量。

• 现在假设y_1=1，也就是令1安培的电流在边1上流动；
• 由图看出y_2也应该为1；
• 再令y_3=-1，也就是让1安培的电流流回节点1；
• 令y_4=y_5=0；

得到一个符合KCL的向量\begin{bmatrix}1\1\-1\0\0\end{bmatrix}，代回方程组发现此向量即为一个解，这个解发生在节点1,2,3组成的回路中，该解即为零空间的一个基。

根据上一个基的经验，可以利用1,3,4组成的节点求另一个基：

• 令y_1=y_2=0；
• 令y_3=1；
• 由图得y_5=1；
• 令y_4=-1；

得到令一个符合KCL的向量\begin{bmatrix}0\0\1\-1\1\end{bmatrix}，代回方程可知此为另一个解。

则N(A^T)的一组基为\begin{bmatrix}1\1\-1\0\0\end{bmatrix}\quad\begin{bmatrix}0\0\1\-1\1\end{bmatrix}。

看图，利用节点1,2,3,4组成的大回路（即边1,2,5,4）：

• 令y_3=0；
• 令y_1=1；
• 则由图得y_2=1, y_5=1, y_4=-1；

得到符合KCL的向量\begin{bmatrix}1\1\0\-1\1\end{bmatrix}，易看出此向量为求得的两个基之和。

接下来观察A的行空间，即A^T的列空间，方便起见我们直接计算
$
A^T=
\begin{bmatrix}
-1 & 0 & -1 & -1 & 0 \
1 & -1 & 0 & 0 & 0 \
0 & 1 & 1 & 0 & -1 \
0 & 0 & 0 & 1 & 1 \
\end{bmatrix}
$
的列空间。

易从基的第一个向量看出前三列A^T的线性相关，则A^T的主列为第1,2,4列，对应在图中就是边1,2,4，可以发现这三条边没有组成回路，则在这里可以说线性无关等价于没有回路。由4个节点与3条边组成的图没有回路，就表明A^T的对应列向量线性无关，也就是节点数减一（rank=nodes-1）条边线性无关。另外，没有回路的图也叫作树（Tree）。

再看左零空间的维数公式：dim N(A^T)=m-r，左零空间的维数就是相互无关的回路的数量，于是得到loops=edges-(nodes-1)，整理得：

此等式对任何图均有效，任何图都有此拓扑性质，这就是著名的欧拉公式（Euler's Formula）。零维（节点）-一维（边）+二维（回路）=1便于记忆。

总结：

• 将电势记为e，则在引入电势的第一步中，有e=Ax；
• 电势差导致电流产生，y=Ce；
• 电流满足基尔霍夫定律方程，A^Ty=0；

这些是在无电源情况下的方程。

电源可以通过：在边上加电池（电压源），或在节点上加外部电流 两种方式接入。

如果在边上加电池，会体现在e=Ax中；如果在节点上加电流，会体现在A^Ty=f中，f向量就是外部电流。

将以上三个等式连起来得到A^TCAx=f。另外，最后一个方程是一个平衡方程，还需要注意的是，方程仅描述平衡状态，方程并不考虑时间。最后，A^TA是一个对称矩阵。

¶