12.【线性代数】——图和网络

图 g r a p h = { n o d e s , e d g e s } graph=\{nodes, edges\} graph={nodes,edges}

上图中，有4个节点（node），5条边(edge)，图上的各个数字为标号。

1.关联矩阵

$$A=\underset{[node1,node2,node3,node4]}{\underbrace{\left[\begin{array}{cccc}-1& 1& 0& 0\\ 0& -1& 1& 0\\ -1& 0& 1& 0\\ -1& 0& 0& 1\\ 0& 0& -1& 1\end{array}\right]}}$$
每一行表示一条边，-1表示开始的节点，1表示结束的节点。第一行表示$edg{e}_1$。
$edg{e}_1$，$edg{e}_2$和$edg{e}_3$现象相关，存在回路（$edg{e}_1+edg{e}_2=edg{e}_3$）。

树：没有回路的图

把图看做是电流图。每一个节点表示电势。两个节点的电势差，形成电流。

2. $A$矩阵的零空间，求解$Ax=0$ 电势

$$A\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}{x}_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_1\\ x_4-x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\end{array}\right]$$
解得：
$$x=c\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$$

$dim(N(A))=1,那么rankA=n-1=\#nodes-1$

3.$A^T$矩阵的零空间，电流

$$A^{T}y=\left[\begin{array}{ccccc}-1& 0& -1& -1& 0\\ 1& -1& 0& 0& 0\\ 0& 1& 1& 0& -1\\ 0& 0& 0& 1& 1\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\\ y_5\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$$
得出：
$$\{\begin{array}{l}-y_1-y_3-y_4=0(合流=0)\\ y_1-y_2=0(流入=流出)\\ y_2+y_3-y_5=0(流入=流出)\\ y_4+y_5=0(合流=0)\end{array}\Rightarrow y=c\left[\begin{array}{c}1\\ 1\\ -1\\ 0\\ 0\end{array}\right]+d\left[\begin{array}{c}0\\ 0\\ 1\\ -1\\ 1\end{array}\right](两个基为图中的回路\#loop)$$

KCL定律： a. 合流 = 0 b. 流入=流出

总结电流图

结论

树：没有回路的图
$dim(N(A^T))=m-r$
$\#loop=\#edges-(\#nodes-1)$

$\#nodes-\#edges+\#loop=1$（对所有图适用）