12.线性代数图和网络
12.【线性代数】——图和网络
图 g r a p h = { n o d e s , e d g e s } graph={nodes, edges} g r a p h = { n o d es , e d g es }
1
3
2
4
5
node1
node2
node3
node4
上图中，有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
=
[
n
o
d
e
1
,
n
o
d
e
2
,
n
o
d
e
3
,
n
o
d
e
4
]
−
1
0
−
1
−
1
0
1
−
1
0
0
0
0
1
1
0
−
1
0
0
0
1
1
每一行表示一条边，-1表示开始的节点，1表示结束的节点。第一行表示
e d g e 1 edge_1
e
d
g
e
1
。
e d g e 1 edge_1
e
d
g
e
1
，
e d g e 2 edge_2
e
d
g
e
2
和
e d g e 3 edge_3
e
d
g
e
3
现象相关，存在回路（
e d g e 1 + e d g e 2
e d g e 3 edge_1+edge_2=edge_3
e
d
g
e
1
e
d
g
e
2
=
e
d
g
e
3
）。
树：没有回路的图
把图看做是电流图。每一个节点表示电势。两个节点的电势差，形成电流。
2. A A A 矩阵的零空间，求解 A x = 0 Ax=0 A x = 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
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
解得：
x
c [ 1 1 1 1 ] x = c\begin{bmatrix} 1\ 1\ 1\ 1 \end{bmatrix}
x
=
c
1
1
1
1
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
d
im
(
N
(
A
))
=
1
,
那么
r
ank
A
=
n
−
1
=
n
o
d
es
−
1
3. A T A^T A T 矩阵的零空间，电流
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}
A
T
y
=
−
1
1
0
0
0
−
1
1
0
−
1
0
1
0
−
1
0
0
1
0
0
−
1
1
y
1
y
2
y
3
y
4
y
5
=
0
0
0
0
得出：
{ − 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)
⎩
⎨
⎧
−
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
oo
p
)
KCL定律： a. 合流 = 0 b. 流入=流出
总结电流图
欧姆定律 y=ce
KCL
电势差 e=x2-x1=AX
电流y1,y2…y5
A^Ty=f=0 f为外接电流
结论
树：没有回路的图
d i m ( N ( A T ) )
m − r dim(N(A^T)) = m - r
d
im
(
N
(
A
T
))
=
m
−
r
l o o p
e d g e s − (
n o d e s − 1 ) #loop = #edges - (#nodes - 1)
l
oo
p
=
e
d
g
es
−
(
n
o
d
es
−
1
)
n o d e s −
e d g e s +
l o o p
1 #nodes-#edges +#loop = 1
n
o
d
es
−
e
d
g
es
l
oo
p
=
1 （对所有图适用）