12.【线性代数】——图和网络
十二 图和网络（线性代数的应用）
图 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（对所有图适用）
助力广东及东莞地区开发者，代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展，成为松山湖开发者首选的工作与学习平台
更多推荐
18
0- 0
已为社区贡献1条内容
所有评论(0)