龙岩市官方网站个人cms网站
十二 图和网络（线性代数的应用）
图 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 = [ − 1 1 0 0 0 − 1 1 0 − 1 0 1 0 − 1 0 0 1 0 0 − 1 1 ] ⏟ [ n o d e 1 , n o d e 2 , n o d e 3 , n o d e 4 ] A=\underbrace{\begin{bmatrix} -1&1&0&0\\ 0&-1&1&0\\ -1&0&1&0\\ -1&0&0&1\\ 0&0&-1&1 \end{bmatrix}}_{[node1, node2,node3,node4]} A=[node1,node2,node3,node4] −10−1−101−10000110−100011
每一行表示一条边，-1表示开始的节点，1表示结束的节点。第一行表示 e d g e 1 edge_1 edge1。
e d g e 1 edge_1 edge1， e d g e 2 edge_2 edge2和 e d g e 3 edge_3 edge3现象相关，存在回路（ e d g e 1 + e d g e 2 = e d g e 3 edge_1+edge_2=edge_3 edge1+edge2=edge3）。
树：没有回路的图
把图看做是电流图。每一个节点表示电势。两个节点的电势差，形成电流。
2. A A A矩阵的零空间，求解 A x = 0 Ax=0 Ax=0 电势
A [ x 1 x 2 x 3 x 4 ] = [ 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 ] A \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} A x1x2x3x4 = x2−x1x3−x2x3−x1x4−x1x4−x3 = 00000
解得：
x = c [ 1 1 1 1 ] x = c\begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix} x=c 1111
d i m ( N ( A ) ) = 1 , 那么 r a n k A = n − 1 = # n o d e s − 1 dim(N(A)) = 1, 那么rankA = n - 1 = \#nodes - 1 dim(N(A))=1,那么rankA=n−1=#nodes−1
3. A T A^T AT矩阵的零空间，电流
A T y = [ − 1 0 − 1 − 1 0 1 − 1 0 0 0 0 1 1 0 − 1 0 0 0 1 1 ] [ y 1 y 2 y 3 y 4 y 5 ] = [ 0 0 0 0 ] A^Ty=\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} ATy= −11000−110−1010−100100−11 y1y2y3y4y5 = 0000
得出：
{ − 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 ) ⇒ y = c [ 1 1 − 1 0 0 ] + d [ 0 0 1 − 1 1 ] ( 两个基为图中的回路 # l o o p ) \begin{cases} -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{cases}\xRightarrow{} y= c\begin{bmatrix} 1\\1\\-1\\0\\0 \end{bmatrix} + d\begin{bmatrix} 0\\ 0\\ 1\\ -1\\1 \end{bmatrix} (两个基为图中的回路\#loop) ⎩ ⎨ ⎧−y1−y3−y4=0(合流=0)y1−y2=0(流入=流出)y2+y3−y5=0(流入=流出)y4+y5=0(合流=0)y=c 11−100 +d 001−11 (两个基为图中的回路#loop)
KCL定律： a. 合流 = 0 b. 流入=流出
总结电流图
结论
树：没有回路的图
d i m ( N ( A T ) ) = m − r dim(N(A^T)) = m - r dim(N(AT))=m−r
# l o o p = # e d g e s − ( # n o d e s − 1 ) \#loop = \#edges - (\#nodes - 1) #loop=#edges−(#nodes−1)
# n o d e s − # e d g e s + # l o o p = 1 \#nodes-\#edges +\#loop = 1 #nodes−#edges+#loop=1（对所有图适用）