Graph & Network
- Incidence Matrix
考慮我們有以下 Graph, 則可以使用右邊 Matrix 代表:
由上可以發現 Edge1, Edge2, Edge3 形成一個 Loop, 而這些 Edges 對應的 Row 形成的 Vector Space 不是 independent! 也就是說如果不形成 Loop 的 Edge 則其形成的 Vector Space 會是 Independent, 反之如果 Vector Space 不是 Independent, 則其中必有 Loop!
上面的 Matrix A 的 Null Space 解會是 Ax=0, 而 matrix x 稱為 Potential nodes; 而要解的方程式成為 Potential differences (Ohm's raw):
可以看出只有一組 x 解為 c*[1,1,1,1], 也就是說 dim(N(A)) = 1 (n-r), 也就是說 Rank=4-1=3!
接著考慮 N(A^T), 也就是解 A^T*y = 0 (Kirchoff's circuit raw):
上式的的 y1+y2+y3=0 說明由 N1 流出的電流需要等於 0; y1-y2=0 說明流進 N2 等於流出 N2 的電流 etc. 此時可以推出 dim(N(A^T)) = m-r (Row space 與 Column space 的 Rank 相等, 即 r=2) -> 5-2 = 3. 而其中的一組 Basis 為 (考慮 Graph 中兩個 roop 的解):
而經過推導可以知道 dim(N(A^T)) 就是 Graph 中 Loop 的數目. 且可以由下面公式決定:
#Node - #Edge + #Loop = 1
最後可以推導出解電路方程式 (下面的 f 為外部 source, 如電源 etc):
沒有留言:
張貼留言