图和网络笔记

1. $AX=0$

一个图可以由节点和边组成，假设我们有一个节点notes ：n=4,边edges：m=5的有向图，表示如下

• 通过以上电路图可以得到关联矩阵(incident matrix),我们定义边，开始端用-1表示，结束端用1表示，用行表示边，用列表示节点。可得如下
  比如edge1是由从节点1出发，到节点2 ，用行向量表示可得
  $$\left[\begin{array}{cccc}-1& 1& 0& 0\end{array}\right]\Rightarrow edge1\text{\hspace{1em}(1)}$$
• 所以矩阵A根据上图可得如下：
  $$A=\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]\text{\hspace{1em}(2)}$$

  • 我们可以看到由边1，2，3组成一个子图，那么看看由1，2，3组成的矩阵表示如下：
    $$\left[\begin{array}{cccc}-1& 1& 0& 0\\ & & & \\ 0& -1& 1& 0\\ & & & \\ -1& 0& 1& 0\end{array}\right]\Rightarrow ro{w}_1+ro{w}_2=ro{w}_3\text{\hspace{1em}(3)}$$
    

    也就是说，如果在矩阵中3行能达到等式关系，可以等效与在图上形成一个子图。

    • 那么矩阵A的零空间代表什么呢？我们将AX=0 用列的形式表示如下：
      $$AX=\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]\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_3\end{array}\right]\text{\hspace{1em}(4)}$$
      $$AX=\left[\begin{array}{c}-1\\ \\ 0\\ \\ -1\\ \\ -1\\ \\ 0\end{array}\right]x_1+\left[\begin{array}{c}1\\ \\ -1\\ \\ 0\\ \\ 0\\ \\ 0\end{array}\right]x_2+\left[\begin{array}{c}0\\ \\ 1\\ \\ 1\\ \\ 0\\ \\ -1\end{array}\right]x_3+\left[\begin{array}{c}0\\ \\ 0\\ \\ 0\\ \\ 1\\ \\ 1\end{array}\right]x_4\text{\hspace{1em}(5)}$$
• AX=0的零空间X表示的是列向量的线性组合。X的物理意义表示的每个节点的电势值[potential at the node ]，那么$x_2-x_1$表示的是edge1的电势差，那什么时候可以保证电势差为0呢，那只有每个结点的电势相同即可，所以可以得到解如下，所以 dim $N(A)=1，Rank(A)=4-1=3$
  $$X=c\left[\begin{array}{c}1\\ \\ 1\\ \\ 1\\ \\ 1\end{array}\right]\text{\hspace{1em}(6)}$$

2. $A^{T}Y=0$

• 矩阵表示形式如下， dim $N(A^T)=m-r(A^T)=5-3=2$,物理上表示$y_1\dots y_5$为每个边edge上的电流大小：
  $$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}-y_1-y_3-y_4\\ \\ y_1-y_2\\ \\ y_2+y_3-y_5\\ \\ y_4+y_5\end{array}\right]=\left[\begin{array}{c}0\\ \\ 0\\ \\ 0\\ \\ 0\end{array}\right]\text{\hspace{1em}(7)}$$
• 函数物理意义:
  $$-y_1-y_3-y_4=0\Rightarrow y_1+y_3=-y_4\text{\hspace{1em}(8)}$$
  表示的对于节点1来说，流入的电流为$-y_4$,流出的电流为$y_1+y_3$，所以可以得到基尔霍夫电流定律，流入节点电流和等于流出节点的电流和
  
• N($A^T$)=m-r=5-3=2，我们看由1，2，3组成的节点环1,如果想成为闭环，可以得到如下：
  $$y_1+y_2-y_3=0\text{\hspace{1em}(9)}$$
• $A^{T}Y=0$的特解中当$y_1=1,y_2=1,y_3=-1,y_4=0,y_5=0$，表示$Loo{p}_{123}$
• $A^{T}Y=0$的特解中当$y_1=0,y_2=0,y_3=1,y_4=-1,y_5=1$，表示$Loo{p}_{345}$
• $A^{T}Y=0$的特解中当$y_1=1,y_2=1,y_3=0,y_4=-1,y_5=1$，表示$Loo{p}_{1234}$
• 线性无关组表示不形成环时的边组合。这样可以看出来矩阵和图的对应关系。很直观。
• 矩阵的相关就是表示图形中的环，矩阵的不相关就是表示不成环，形成树。
  
• 矩阵的秩和图之间的关系

1. D i m { N ( A T ) } Dim \{N(A^T)\} Dim{N(AT)}=#loops;
2. m=#edges;
3. r=n-1,节点的数量-1
   D i m { N ( A T ) } = m − r (10) Dim \{N(A^T)\}= m-r\tag{10} Dim{N(AT)}=m−r(10)
   综上所述，可以得到如下

$$\#nodes-\#edges+\#Loops=1\text{\hspace{1em}(11)}$$

3. $AX=0$和 $A^{T}Y=0$的关系

• 在$AX=0$ 的方程中，我们定义每个边两端的电势差E
  $$E=AX\text{\hspace{1em}(12)}$$

• 在$A^{T}Y=0$的方程中，我们定义每个边中的电流为y,通过欧姆定理，定义电势差E，和常数C，电流Y之间的关系如下：
  $$Y=CE\text{\hspace{1em}(13)}$$

• 电流方程如下：
  $$A^{T}Y=0\text{\hspace{1em}(14)}$$

• 将方程12,13 代入到方程14中可得如下：
  $$A^{T}CAX=0\text{\hspace{1em}(15)}$$

• 我们定义外部电流从原来的0变为f,整理公式15可得平衡方程，并且$A^{T}CA$对称：

$$A^{T}CAX=f\text{\hspace{1em}(16)}$$