线性代数12-矩阵应用:图与网络

Linear Algebra-矩阵应用:图与网络-12

一、知识概要

本节重点阐述图与矩阵之间的紧密联系，借助矩阵来展现图的特性。与前面几节内容不同，之前例子中的矩阵元素大多是为解释性质而设定的，而本节矩阵元素均源于实际问题，这能更直观地体现之前所学矩阵性质在实际场景中的应用价值。

二、图和关联矩阵

我们先来看一个有向图（图一）：

在本节中，我们围绕这个有向图展开研究。对于有向图，我们可以写出它的关联矩阵 $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]$$

对于不太熟悉关联矩阵的读者，这里简单介绍一下。在这个 $5\times 4$ 的矩阵中，每一列对应一个节点，例如第一列代表节点 1，第二列代表节点 2，以此类推；每一行则代表一条边的走向，第一行代表边 1，第二行代表边 2，依此类推。需要注意的是，在每一行所代表的边中，若该边以某个节点为起点，那么在矩阵中对应元素为 -1；若以某个节点为终点，对应元素则为 1。

以第一行为例，第一行代表边 1 的特征。在图（一）中，边 1 从节点 1 出发，到达节点 2，这在矩阵中就表现为 $A_{11}=-1$，$A_{12}=1$。其他行以此类推。

接下来，我们探讨图（一）所代表的实际意义。

【例】假设 $x$ 表示每个节点上的电势，研究 $Ax=b$ 这种形式能得出哪些结论。

1. 当 $b$为零向量时：此时需要求解 $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_1\\ x_4-x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\end{array}\right]$$

求解上述方程组可得：$x=C\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$（$C$ 为常数）。

因为 $x$ 代表各个节点的电势，所以 $x$ 的解集表明当 $b=0$ 时，各点电势必须相等。我们知道，电势差与电流的形成密切相关，$b=0$ 意味着各条边上都没有电流（即电势差为零），而最终解得各点电势相等时边上电流为 0，这与我们的物理常识相符。

1. 当 $b$不为零时：我们可以通过特解加上通解的方法，求出在不同 $b$ 值情况下方程的解。这些解代表了在不同电势差情况下，各点电势的大小。

接下来研究左零空间 $A^{T}y=0$ 的特点。首先，矩阵 $A$ 的转置为：

$$A^T=\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]$$

然后求解方程 $A^{T}y=0$，即：

$$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}0\\ 0\\ 0\\ 0\\ 0\end{array}\right]$$

A转置后，$y$ 有五个分量，是对 $A^T$ 的行进行线性组合。由于 $A^T$ 的行代表 1 - 5 边，结合前面的例子背景，这里求解的就是流过每条边的电流。

求解该方程可得：

$$-y_1-y_3-y_4=0$$$$y_1-y_2=0$$$$y_2+y_3-y_5=0$$$$y_4+y_5=0$$

这些方程体现了基尔霍夫定律，即每个节点流入和流出的电流相同。每个方程分别代表一个节点的电流情况，最终解得的 $\left[\begin{array}{ccccc}{y}_1& y_2& y_3& y_4& y_5\end{array}\right]$ 就是满足这一特性的各条边的电流值。

三、实际应用的扩展

$Ax=\left[\begin{array}{ccccc}{x}_2-x_1& x_3-x_2& x_3-x_1& x_4-x_1& x_4-x_3\end{array}\right]$，这个式子表示每两点之间的电势差。该方程将图的特征（通过矩阵 $A$ 体现）与各点电势（x）紧密联系起来。

在研究 $A^{T}y$ 时，其中的 $y$ 代表各个边上的电流。结合电流与电势差的关系，我们联想到初中所学的欧姆定律。电流与电压之间存在一个比例系数，假设用矩阵 $C$ 表示，即有：

$\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right]=C\left[\begin{array}{c}{x}_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_3\end{array}\right]=CAx$，也就是 $y=CAx$。

这样，我们就成功地用矩阵表示了图像、电流和电势差这些概念。

进一步拓展，前面研究的 $A^{T}y=0$ 是无源场的情况。如果存在外加电源，可表示为 $A^{T}y=f$（$f$ 表示外加电源的影响）。结合前面得到的 $y=CAx$，最终得到式子：$A^{T}CAx=f$。

四、学习感悟

本节内容与之前所学知识联系紧密，同时与实际应用的结合也十分紧密。从一个有向图出发，结合实际物理问题，详细解释了如何运用矩阵来阐述欧姆定律和基尔霍夫定律。学习完本节后，我们对之前所学的各种空间在实际问题中的作用有了更深入、更切实的理解，真正体会到线性代数知识的实用性和广泛应用。