Linear Algebra – Lesson 12. 图和网络

Schedule

  • Graphs & Networks
  • Incidence Matrices
  • Kirchhoff’s Laws

Graph – 图

Graph : Nodes, Edges 图由节点和边构成.
potential : 电势
potential differences : 电势差
currents : 电流
图中节点和边的信息用关联矩阵(Incidence Matrix)来表示.
上图中的相关信息可以用如下关联矩阵表示,其中列和行分别表示第x个节点和不同的边,-1表示边的起点,1表示边的终点:
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}
其中边1,2,3构成一个回路.
在图中,回路的数量和位置至关重要.
A中可以看出,行1,2,3是相关的,对应的分别是边1,2,3, 所以回路意味着相关(loops correspond to dependent).
与回路对应的行是线性相关的.
因为一条边只与两个节点相关,所以关联矩阵中每行只有两个非零值,该矩阵是一个稀疏矩阵(sparse matrix).

那么矩阵A的零空间是什么样的?
零空间是否只有零向量意味着A中各列是否线性相关.
我们可以通过求解Ax=0来确定矩阵A的零空间.
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_1-x_2\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 = x_1,x_2,x_3,x_4 \text{(potentials at nodes)}\
\rightarrow x_2-x_1,etc. \text{(potential differences)}\
\rightarrow y_1,y_2,y_3,y_4,y_5\text{ current on edges (Ohm’s Law) }\
\rightarrow A^Ty=0\text{(Kirchoff’s Current Law)}
可以解出一个解为 x=\begin{bmatrix}1\1\1\1\end{bmatrix}
零空间的一组基其实就是上述的解,因为零空间是一维的(???为什么是一维的???),将x乘以常数c就是整个零空间,具体表现为四维空间中的一条直线 .
如果各节点的电势相等,则不会出现电流. 根据求出的解,将x_4的电势设为0(接地点),则其他点的电势也就可以求出,同时矩阵的秩也可以求出为3.

对于N(A^T)来说,A^Ty=0,dimN(A^T)=m-r
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}
根据KCL可以得出 -y_1-y_3-y_4=0\ 表示节点1的合电流为0.
第二行为y_1-y_2=0,说明结点2流入电流等于流出电流.
同理,y_2+y_3-y_5=0,y_4+y_5=0.

对于结点1,2,3构成的回路,可以得出零空间中的一个向量\begin{bmatrix}1\1\-1\0\0\end{bmatrix}
同理,对于结点1,3,4构成的回路,可以得出零空间中的另一个向量\begin{bmatrix}0\0\1\-1\1\end{bmatrix}
在结点1,2,3,4构成的回路中, 解出的向量将是上述两个向量的线性组合.
A中得到没有回路的结构,y_1,y_2,y_4, 表示的是没有回路的图,也就是树(Tree).
dimN(A^T) = m-r \rightarrow # loops = # edges – (# nodes -1) (rank = n-1)
从而得到欧拉公式(Euler’s formula) # nodes – # edges + # loops = 1

将电势差记做e, 则e=Ax, y=Ce(电势差导致电流的产生),A^Ty=0(电流满足KCL定律方程),这是在无电源的情况下对应的方程.
如果存在外部电流源f,则A^Ty=f,从而求得A^TCAx=f.

留下的问题: 可以从A^TCAA^TA中得到什么?

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据