10-1-图与网络
一句话概括
一张图(graph)可以被写成一个矩阵:关联矩阵(incidence matrix) 的每一行对应一条边,行中只有两个非零元 与 ,分别标记这条边的起点与终点。于是「图论问题」被翻译成「 的四个基本子空间问题」: 是"电势可整体加常数", 是回路(独立回路数), 是可实现的边落差(KVL 就住在这里), 是可实现的节点注入(电荷守恒就住在这里);而 就是图的拉普拉斯矩阵(graph Laplacian) (度矩阵减邻接矩阵)。把电流定律、欧姆定律、电压定律串起来,就得到 。
本篇覆盖:图作为线性代数对象、关联矩阵的构造(用一个 节点 边的例子写出完整矩阵)、四个基本子空间在图上的物理意义与维数、用秩—零化度定理论证欧拉公式(Euler's formula)、基尔霍夫电流定律(KCL)与电压定律(KVL)的矩阵形式、拉普拉斯矩阵 的五条性质与谱解释、最小生成树(minimum spanning tree)与最短路中线性代数的角色、一段可运行的 numpy 代码(构造 、验证 、数零特征值个数得到连通分量数)、电路与社交网络的应用,以及通往 10-2-Markov矩阵与稳态 的 PageRank 图基础。
这是「用一张图解释整个 18.06」的一节,也是把四大子空间从抽象符号变成电路、地图、社交网络的最短路径。
一、定义
1.1 图是线性代数的对象
定义 10.1.1(图,graph) 一个图 由两部分组成:
- 节点集(vertex set / node set) ,共 个节点(也叫顶点);
- 边集(edge set) ,共 条边,每条边连接两个节点。
若边没有方向,称 为无向图(undirected graph);若每条边都指定了从起点到终点的方向,称 为有向图(directed graph)。若任意两个节点之间都能沿着边走通,称 是连通的(connected),否则它分裂成若干个连通分量(connected component)。
图的"谁连着谁"是组合信息,本身不是线性对象。变魔术的一步是把"哪条边连哪两个节点"写进一个矩阵。
定义 10.1.2(关联矩阵,incidence matrix) 设 有 个节点、 条边,且每条边都指定了方向(无向图就人为约定一个方向)。定义 矩阵 ,其第 行对应第 条边:
逐条翻译成中文: 当且仅当节点 是边 的起点; 当且仅当节点 是边 的终点;其余情况为 。也就是说:一行一条边,起点记 、终点记 ,其余全为 。
也就是说:一行一条边,起点记 、终点记 ,其余全为 。
先说清楚形状约定,因为全篇公式都依赖它
本库统一采用 (行 = 边,列 = 节点) 的关联矩阵。理由有三条,缺一不可:
1. 这样 是 的节点矩阵,恰好等于拉普拉斯矩阵 (3.6 节会逐项验证),而 正是本篇的主角 ;
2. 这样物理方程的形状全部标准: 是节点量, 是边量,()把节点量变成边量(差分),也把边量汇总成节点量(求和);
3. 这与 Strang 教材、MIT 18.06 第 12 讲的记号一致( 是那一讲的招牌结论)。
不同教材的关联矩阵常常互为转置(有的写 ,即列 = 边)。这不改变数学,但会让所有公式的长相互换。最典型的一个例子是 KCL 的非齐次形式:
- 本篇(行 = 边):,其中 是节点上的"净注入"( 维);
- 列 = 边的写法:同一个物理方程写成 (此时 是 维的边向量)。
"齐次"情形(无外部注入)两种写法长得一样:本篇是 ,列 = 边的写法是 ——都是"每个节点的净注入为零",只是矩阵互为转置。所以读任何资料前,第一步永远是确认形状: 是几行几列。
1.2 一个具体的例子: 节点、 条边
取 个节点、 条边,约定方向如下:
e1 : 1 -> 2
e2 : 2 -> 3
e3 : 4 -> 1
e4 : 2 -> 4
e5 : 4 -> 3
文字示意图(箭头是人为选定的方向):
e2 e5
(2) ------> (3) (4) ------> (3)
^ ^
| e1 | e4
(1) <----------------+
e3 (方向 4 -> 1)
按定义 10.1.2 逐行填写(第 行对应边 ):
- 第 1 行():节点 1 为 、节点 2 为 ;
- 第 2 行():节点 2 为 、节点 3 为 ;
- 第 3 行():节点 4 为 、节点 1 为 ;
- 第 4 行():节点 2 为 、节点 4 为 ;
- 第 5 行():节点 4 为 、节点 3 为 。
于是
逐行验证第 3 行:边 的方向是 ,所以节点 4(起点)的位置是 、节点 1(终点)的位置是 ,即 ✓。
三十秒自查表
1. 是 ;
2. 每一行恰好两个非零元,一个是 、一个是 ;
3. 每一行的和都为 (),于是 ;
4. 每一列的和也为 (每条边在起点列贡献 、在终点列贡献 ),于是 ;
5. 若某条边是自环(起点 = 终点),这一行会全零——自环对关联矩阵"不可见",本章通常先假定无自环。
第 3、4 条给出两个"天生的零空间向量",1.4 节会反复使用。
1.3 三个马上能算的量
(1) 秩 。 对上面的 做消元(行化简的通用手法见 2-2-消元法的思想)。先找一个线性关系:第 3 行 与第 1、2 行满足
所以 ,第 3 行是前两行的组合。再看第 1、2、5 行 :若 ,由第 3 列得 ,由第 4 列得 ,由第 1 列得 ,故 ,三者线性无关。于是
(2) 零空间 的维数。 是 ,有 个未知数、秩 ,由秩—零化度定理(rank-nullity theorem)
(3) 左零空间 的维数。 是 ,有 个未知数、秩 ,所以
这三个数 、、 就是本篇的主角。先把每个数"是谁的维数"标清楚,再谈物理意义(这张对应关系是全篇最容易搞错的地方,1.4 节会给出严格证明):
| 量 | 它是什么空间的维数 | 物理意义 |
|---|---|---|
| 的秩 列空间的维数 行空间的维数 | 节点侧可用模式数 | |
| 零空间(节点空间里的解集 ) | 电势可整体加常数(,连通时为 ) | |
| 左零空间(边空间里的环流) | 满足 KCL 的环流,独立回路数() |
一句话记法: 管"电势加常数", 管"回路"。 下面两节分别把这两句话证出来。
1.4 两个"天生的向量"与两句话的严格证明
第一句话: 就是"电势可整体加常数",维数 。
的每一行和为 (一行就是"一个 加一个 "),所以
(注意形状: 是 ,,所以 且等于 ✓。)
这句话的含义: 意味着"所有节点电势都取同一个值",此时 的每个分量都是"",即所有边的落差为零——电势加一个常数不会被差分算子察觉到。
反过来:设 ,即 。 的第 个分量对应边 ,等于
每一条边两端的节点, 的分量都相等。 沿路径走过去(同一连通分量内任意两点都有路径),得到: 在每个连通分量上取常数值。若第 个连通分量是 ,令 为"在 上取 、其余取 "的向量,则
对连通图():
(线性无关性:这些 在互不相交的坐标集上取 ,任一非平凡组合都至少有一个非零分量。)这就是 1.3 节表格里那句话的完整证明。
第二句话:,即"每条边挂 个单位的均匀环流"。
的每一列和为 (每条边在起点列贡献 、在终点列贡献 ),把每列加起来就得到
(形状: 是 ,,故 且等于 ✓。)
这句话的含义: 表示"每条边上都挂 个单位的流量,方向沿各边约定方向"。此时每个节点的净流入 ——流入流出恰好抵消,所以它是一个"处处均匀的环流",满足无源无汇的 KCL。因此 属于 ,而且它是 维空间里的向量(这是它与 最本质的区别)。
两个 住在不同空间,别混
- (长度 = 节点数)满足 ,由此推出 (连通时),代表电势整体加常数;
- (长度 = 边数)满足 ,由此得到 里的一个向量,代表均匀环流。
判断标准极简单:看向量有几个分量(有多长)。 有几项,就知道它在哪个空间里。这是本章第一大错源。
二、几何直观
2.1 关联矩阵在做什么: 是差分, 是求和
把节点上的量变成边上的量(差分)。 给每个节点 一个实数 (例如电势,potential),组成 ,计算 ( 是 ,结果是 维的边向量,每个分量对应一条边):
第 1 个分量 ,正是边 ()终点的电势减起点的电势。第 3 个分量 : 的方向是 ,"终点减起点" ✓。
逐个分量的几何含义: 的每一个分量都是"某条边两端的电势差"。这就是 的作用——把节点上的高度函数,变成每条边上的落差。
一句话图像
是图上的差分算子(difference operator),也是"梯度算子"的离散版本:节点 → 边,取落差。反过来 把边上的量汇总到节点上,是"散度算子(divergence operator)"。
中学物理的"高度差"、微积分的"导数"、这里的"图上的差分"是同一件事的三个版本。 就是"先差分、再把平方和送回来",这正是二阶差分(拉普拉斯算子)的离散版本——这就是它叫"拉普拉斯矩阵"的原因。
把边上的量汇总到节点上(求和)。 设 是每条边上的电流(current),则 ( 是 ,作用在 维的边向量上得到 维的节点向量):
读第 1 个分量 :节点 1 连着 (,节点 1 是起点,系数 )与 (,节点 1 是终点,系数 )。
关键约定(后面所有公式都由它决定):约定 表示电流沿边 的方向从起点流向终点。于是
逐条翻译: 表示"对一切以节点 为终点的边求和", 表示"对一切以节点 为起点的边求和"。于是 就是"流进节点 的总量减去流出节点 的总量",即节点 的净流入。
记住这一条,本章的符号再也不会错
在"行 = 边、起点 、终点 "的约定下, 给出每个节点的"净流入"。
物理上"净流入"就是外部注入的电流(注入,injection)。所以 KCL 的最干净写法是
(式中 即"节点净注入向量",中文含义写在公式外面,避免在 MathJax 中使用中文。)
以后遇到符号可疑的情况,就回到这一句:" = 净流入"。
若习惯用"净流出"(即 的相反数)写 KCL,只需把右端换成 ;或者等价地,把 的每一行都乘 (即把所有边的方向反过来)。三种写法数学上完全等价,唯一的要求是全篇一致。
2.2 零空间:电势可以整体加一个常数
解 ,(节点上的量):
由第 1 式 ,由第 2 式 ,于是 ;由第 3 式 ,所以四个分量全部相等。取 :
与 1.3 节算出的维数一致。几何图像:把整张图的电势同时抬高 ,每条边的落差一字不改,所有电流一字不改。所以"电势的绝对值"在图上没有意义,只有差值有意义——这既是 的物理内容,也是"电压零点可以任选"(接地)的线性代数根源。
一般情形:如果图分裂成 个连通分量,则 只要求"同一条边两端相等",也就是"同一个连通分量内相等",于是
这就是"连通分量的个数"这个纯组合概念,第一次以维数的身份出现在矩阵里。
2.3 左零空间:回路与 KCL
解 ,(边上的量)。先把它读清楚: 意味着"对每个节点 ,与它相连的边上的 按 求和为零",也就是"若把 看成每条边上的流量,则每个节点的净流入为零"。写出每个节点一个方程:
四个方程分别对应节点 1、2、3、4(这是关键: 是"每个节点的净流入为零")。
由第 1 式 ;由第 3 式 ;代入第 2 式 ;第 4 式自动成立(冗余,正好反映 )。取自由参数 、:
所以一组基是
逐条读 : 上取 ,其余取 。三条边分别是 、、,首尾相接构成三角形 ,每条边都取 ,正是"沿这个三角形绕一圈"。
逐条读 : 取 ()、 取 ( 反向,即 )、 取 ( 反向,即 )。得到三角形 。
左零空间的几何图像:回路空间(cycle space)****
的每个向量都是"若干部绕圈环流"的叠加,维数 就是独立回路数(independent loops)。
验证"独立":,这是外圈 的环流(中间那条 被两条路径共用,所以系数是 )。这张图上一眼能看到的圈有 个(两个三角形 + 一个外圈),但只有 个独立——外圈是前两个的差。这就是"独立回路数"三个字的全部含义。
2.4 列空间与行空间:可实现的落差与可实现的注入
(边空间),维数 。 它是 的列的线性组合的全体。由 2.1 节,每个 都是"某个电势场产生的落差向量",所以 正是"可实现的落差模式"的集合。
由 4-1-四大子空间的正交性,,即
即: 在 里,当且仅当它与每一个回路向量正交。
用 2.3 节算出的回路向量检验:取 与 :
(三条边首尾相接,端点两两抵消。)同理 ✓。
这就是基尔霍夫电压定律(KVL)的"回路版":落差能写成电势差,当且仅当沿每个闭合回路的电压降代数和为零。线性代数里的"正交"就是物理里的"做功为零"——任取环流 与任意电势场,。
(节点空间),维数 。 它是 的列空间(即 的行空间),由 的 个行向量张成。由 2.1 节,每个 都是"某个电流分布造成的节点净注入",所以 正是"可实现的注入模式"的集合。
它恰好是 ,而 ,所以 中的每个 都与 正交,即
这就是电荷守恒:注进去的电流必须全部抽出来,所以各节点注入之和为零。
可解性条件的图上版本: 有解当且仅当 ,而 ,所以在 中这个条件就是"与 正交",即 。物理上就是"注进去的电流必须全部抽出来"。 这是 3-3-Ax=b的完整解 可解性条件在图上的化身。
2.5 四个基本子空间的汇总表(务必背下这张表)
是 (本例 ),秩 (本例 ,):
| 空间 | 定义 | 住在 | 维数 | 物理意义 |
|---|---|---|---|---|
| (节点) | 电势整体加常数(每个连通分量一个) | |||
| (节点) | 可实现的净注入模式 () | |||
| (边) | 可实现的落差模式 ( 即 KVL) | |||
| (边) | 独立回路(环流) |
对本例的具体结果:
- ,维数 ;
- ,维数 ,对应两个独立回路(三角形 与三角形 );
- ;
- 秩—零化度定理逐项核对: ✓; ✓。
一句话总结这张表
是"电势的自由度"(每个连通分量一个常数), 是"回路的个数"(独立回路数)。
连通图恰好使两者都是一维(一个连通分量、一个独立回路……更准确地说:连通时 故 ,而 ,只有当 时它才等于 )——但无论如何,区分方法始终是"看向量有几个分量": 个分量的是节点量(对应 里的 ), 个分量的是边量(对应 里的回路)。
三、性质与定理
本篇此后统一使用的记号
- : 关联矩阵,行 = 边、列 = 节点,起点 、终点 ;
- :节点电势;:边落差(终点减起点);:边电流(, 为电导);
- :节点净注入;:加权拉普拉斯矩阵();
- ( 为连通分量数)。
3.1 定理:连通图的关联矩阵秩为
定理 10.1.1(关联矩阵的秩)
设 有 个节点、 条边、 个连通分量, 是 关联矩阵,则
特别地,若 连通(),则 。
证明(走 1.4 节已经铺好的路,一次做完)
第一步:。
设 ,即 。看第 个分量(对应边 ,设它从节点 指向 ):
也就是说:每一条边两端的节点, 的分量必须相等。 沿路径一路走过去(同一连通分量内任意两点都有路径),得到:在同一个连通分量内, 的分量全相等。
设第 个连通分量为 ,令 为"在 上取 、其余取 "的向量。由上一段 ,即 ;这些向量在互不相交的坐标集上取 ,线性无关,故 。反过来,任何 在每个连通分量上取常数,可唯一写成 ,故 。合并得
第二步:。
对 (,有 个未知数)用秩—零化度定理:
第三步(附带):。
对 (,有 个未知数)用秩—零化度定理,秩相同仍为 :
连通时 ,即得 (独立回路数,3.3 节)。
这个证明值得记住的两句话
1. " 迫使每条边两端相等" ⟹ 连通分量内取常数 ⟹ 每个连通分量贡献一个自由度,故 ;
2. 秩的公式 是秩—零化度定理的直接推论,不需要额外的技巧。 时 ,即"电势整体平移恰好一维"。
3.2 定理:欧拉公式就是秩—零化度定理
定理 10.1.2(欧拉公式,Euler's formula)
设连通图 有 个节点、 条边、 个独立回路,则
证明 对 的 用秩—零化度定理。未知量个数是列数 :
(用了定理 10.1.1:连通时 )。另一方面,对 ()用秩—零化度定理,未知量个数是列数 :
而 3.3 节将证明 正是独立回路数 。代入并整理:
用 1.2 节的例子检验:、、,则 ✓。
与秩—零化度定理的逐项对应(本篇的核心洞察):
两条式子相减整理即得欧拉公式。换句话说:欧拉公式不是图论里一条孤立的神秘公式,它就是秩—零化度定理对关联矩阵的一个特例。 详见 3-5-四大子空间的维数。
一般连通分量数 的版本
验证:两个互不相连的三角形,、、,则 ✓。
3.3 定理: 等于独立回路数
定理 10.1.3(回路空间的维数)
对任意图(可以非连通),。对连通图,,等于独立回路数(也等于"生成树的补边数")。
证明思路(完整证明需要生成树的概念)
取 的一棵生成树(spanning tree) :连通、不含圈、包含全部 个节点的子图,它恰有 条边(每加入一个节点就加入一条边)。不在 中的边有 条,称为弦(chord)。
对每条弦 ,在 中存在唯一的路径连接 的两个端点(树上两点的路径唯一),于是"弦 + 这条路径"构成一个圈。给这个圈定向,就得到 中一个非零向量:圈上的边取 (与圈方向一致取 ,相反取 ),圈外的边取 。
这些向量线性无关:每条弦只出现在它自己那个圈里(因为圈由弦与树上路径组成,而别的圈用别的弦),所以用"看各弦位置的坐标"即可判定无关。于是 。另一方面由秩—零化度定理与定理 10.1.1:
连通时 ,两者相等,证毕。
适用条件:无自环(自环行全零,需单独当作一个独立回路处理)。
3.4 定理:接地定理(删掉一行就满秩)
定理 10.1.4(接地定理)
设 连通, 是 关联矩阵。删去 的任意一列,得到 矩阵 ,则 ,即 列满秩,且 (在 维空间里)。
证明思路 删掉一列相当于把那个节点选为"参考节点"(接地,ground),它的电势被固定为 (不再作为未知量)。删列后未知量有 个,方程仍是 个。由于 的零空间由 张成,而删掉一个分量后 不再是零空间的向量(它的分量不全相等地"整周平移"——具体地说,若 且把 补一个 得到 ,则 只在被删掉的那一列对应的位置可能非零;但 的每行和为 给出 ,即 的分量之和为零,而它只有一个分量可能非零,故该分量为零),于是 ,从而 ,即 ;但 的第(被删)分量为 ,故 ,。所以 ,。
工程含义:接地 = 消除"电势可整体平移"的自由度,让 有唯一解。这解释了为什么电路仿真软件必须要求"至少接地一个节点"——不接地就有一个自由度没定,矩阵奇异。
3.5 基尔霍夫定律的线性代数表述
三条物理定律,三个矩阵等式(统一用 的 ,物理方程通过 表达):
| 物理定律 | 文字表述 | 矩阵形式 |
|---|---|---|
| KCL(基尔霍夫电流定律,Kirchhoff's Current Law) | 每个节点的净注入 = 外部注入 | ;无外部注入时 |
| 欧姆定律(Ohm's Law) | 边电流 = 电导 × 边落差 | , |
| KVL(基尔霍夫电压定律,Kirchhoff's Voltage Law) | 边落差 = 两端电势差(终点减起点) |
把三者串起来(形状决定一切: 是 , 是节点量, 是边量):
即
形状检查: 是 、 是 、 是 ,乘积是 ✓,作用在 上得到 ✓。完全自洽。
这正是本篇要的结论: 是 的加权拉普拉斯矩阵(weighted Laplacian),当所有电导 (每条边 ,)时
对称、稀疏、半正定——这正是数值线性代数里最想看到的矩阵结构,也是本篇标题里"图"与"网络"最终落到 上的原因。
三条定律的最终版本(本篇只用这一版,请抄在笔记本第一页)
其中 是 (行 = 边,列 = 节点), 是节点电势, 是边落差与边电流, 是节点净注入。
记忆法: 把节点变成边(差分), 把边变成节点(求和)。 判断"该用 还是 "只需问一句:这一步的输入住在哪个空间? 输入是节点量( 维)就用 ,输入是边量( 维)就用 。
定理 10.1.5(KVL 的等价说法:回路版)
当且仅当对每个回路 有 。也就是说:"电压降可用电势差表示"等价于"沿任意闭合回路的电压降代数和为零"。
证明 由 4-1-四大子空间的正交性,。于是 对 的一组基(即每个独立回路)都有 。
这就是 KVL 的"回路版"与"电势版"的等价性:中学课本说"绕一圈电压降为零",线性代数说" 落在 里",两者是一回事。
3.6 图的拉普拉斯矩阵
定义 10.1.3(图的拉普拉斯矩阵,graph Laplacian)
设 是无向图(边上可有权重 ), 是 关联矩阵,。定义
它有闭式 : 是度矩阵(degree matrix), 是邻接矩阵(adjacency matrix)( 若 相连且 ,否则 )。逐元素:
逐条翻译:对角元 等于节点 的加权度数(与 相连的所有边的权重之和); 当 且 与 相连; 当 且 与 不相连。(符号 表示"相连"。)
用 1.2 节的例子验证。 是 , 是 :
独立重算一个元素以确认: 的第 1 行(即 的第 1 列)与 的第 3 列的内积。 的第 1 列(节点 1 那一列),第 3 列 ,内积 ✓(节点 1 与 3 不相连)。再看 :第 4 列 ,内积 ✓(节点 1 与 4 相连于 )。
逐项核对闭式 :度数 (节点 1 连 ;节点 2 连 ;节点 3 连 ;节点 4 连 ),对角线正是 ✓; 对应"不相连" ✓;每行之和 ✓。
手写 的四条检查(比结论更重要)
1. 对角元 = 度数,且 ;
2. 非对角非零元 的位置必须与边一一对应:第 行非零的非对角元个数 ;
3. (每条边贡献两个端点);
4. 最保险的一条:用程序验
L == A.T @ A(见 4.4 节代码里的assert)。凭图的形状"顺手写 "是最常见的错误来源——尤其容易把"不相连"误写成 。
性质清单(五条,每条给理由)
- 对称:( 对角故对称)。适用条件: 对称。
- 半正定(positive semidefinite):对任意 ,
把 展开(它就是边 的落差 ):
(求和号下的 "edges " 表示"对一切边 求和"。)
物理解释:这正是电路的总功耗。 数学解释:它是"离散 Dirichlet 能量",度量 在图上有多不平滑。
- 每行和为 (等价地 ):由闭式,第 行和 。故 , 一定奇异()。这与"电势可整体加常数"是同一件事: 里 只以差值出现。
- 连通分量数 :由第 2 条的展开式, 当且仅当每条边两端相等;由定理 10.1.1 证明中的同一论证,这当且仅当 在每个连通分量上取常数。这些向量恰构成 ,故
注意:这里 与 维数相同、物理含义相同(都是"每个连通分量内加常数"),因为二者都由"边两端相等"这一条件刻画。(这与 2.3 节的 完全不同——后者的向量住在 ,是回路。)
- 特征值非负实数:由第 1、2 条(实对称半正定), 有 个实特征值 ,可正交对角化 (见 6-4-对称矩阵与正定矩阵)。连通时 单重、;一般情形 的重数恰为 。
把上面的性质用例子全部验一遍: 的迹 ✓;特征多项式为
所以特征值是
零特征值恰好 个 ⟹ 连通分量数 (图连通)✓;特征值之和 ✓;平方和 ✓(这是一条可用的自查恒等式); ✓。
3.7 谱与连通性、聚类
对连通图,记特征值 。
- 称为代数连通度(algebraic connectivity): 越大,图越"难被切成两块",连通性越强。
- 路径图 : 大时 极小——一条长链很容易从中间剪断;
- 完全图 :——每个节点都连所有其他节点,切不开;
- 本篇例子:,介于两者之间;
- 若图由 个"几乎不相连"的簇组成,则 有 个接近 的特征值(硬聚类:完全不连则恰有 个零特征值)。
- Fiedler 向量(对应 的特征向量)给出"最佳二分":正分量归一类、负分量归另一类。对本例, 满足 (验证:第 1 行 ;第 3 行 ;第 2、4 行 ✓),于是节点分成 与 。这就是谱聚类(spectral clustering)的起点。
- 矩阵—树定理(Matrix-Tree Theorem,了解即可):连通图的生成树个数等于 的任意一个代数余子式,也等于 。对本例:,而 去掉第 1 行第 1 列的 主子式也等于 ✓。这张 节点 边的图恰有 棵生成树。
3.8 最短路径、最小生成树与网络流中的线性代数
这三类经典算法本身是组合算法,但它们的结构表述与最优性证书都写成线性代数/线性规划的形式:
- 最小生成树(minimum spanning tree, MST):在连通图中选 条边把所有节点连起来、总权重最小。它的线性代数含义有两层:
- 生成树 = 关联矩阵中线性无关的 列。因为 ,任取 列若线性无关,就确定一棵包含所有节点的树;多余的列必是这些列的线性组合。于是"最小生成树 = 在 的所有满秩 列子集中找权重最小的一组"——组合优化被翻译成了线性代数。
- 树上 :树上没有回路,维数 ✓。
经典算法是 Kruskal 贪心:按权重从小到大加边,若成圈则丢弃。用 scipy 可一行计算(见 4.4 节)。
- 最短路径(shortest path):把边看成电阻,则两点间等值电阻 = 在 间注入单位电流时两点的电势差:
其中 是 Moore–Penrose 广义逆。这把"电阻网络的有效电阻"与"随机游走的首次命中时间"联系起来,是图嵌入(graph embedding)与半监督学习的基础。
- 网络流(network flow):最大流问题写成线性规划,约束矩阵正是关联矩阵:流量守恒 与容量约束 。最大流—最小割定理(max-flow min-cut theorem)是线性规划对偶定理的特例——这把图论、线性代数与第 10.3 节的线性规划连成一条线。
四、计算方法与步骤
4.1 构造关联矩阵的标准流程
- 给节点编号 ,给边编号 (顺序任意,但要记下来);
- 给每条无向边人为指定方向并写下边表(例如"");
- 开一个 的零矩阵(行 = 边,列 = 节点),逐行填:第 条边 ,则位置 填 、 填 ;
- 自查:每行恰好两个非零元、行和为 ;每列和也为 ;若某行全零,说明漏了方向(自环除外);
- 顺手记下度数列 ,用于交叉验证 。
4.2 求四个基本子空间的基(图上的专用写法)
记 为节点数、 为边数、 为连通分量数、。
- 秩:;连通时 。数 用并查集或广度优先搜索。
- (节点空间,维数 ):对每个连通分量取"该分量上全 、其余为 "的向量。连通图时就是 。
- (边空间,维数 ):先求一棵生成树,对每条弦 找出树上 的唯一路径,"弦 + 路径"组成圈,沿圈定向给每条边赋 。
- (节点空间,维数 ):取 的 个线性无关列即得基,等价于取 的 个线性无关行。物理上它是"可用注入模式",且每个基向量都与 正交。
- (边空间,维数 ):取 的 个线性无关列即得基,即"可用落差模式";由定理 10.1.5,它恰是"与所有回路正交"的落差全体。
4.3 解电路方程
- 接地:选定参考节点 ,令 ,删去系数矩阵的第 行与第 列(得到 可逆矩阵,定理 10.1.4);
- 可解性检查:(电荷守恒),否则无解——这是 3-3-Ax=b的完整解 可解性条件在图上的化身;
- 解线性方程组得 ;
- 回代 得边落差(终点减起点);
- 回代 得边电流;
- 自检:(KCL)与 (功率守恒)。第 6 条同时检查了 、、、 四处,是最强的自检。
4.4 可运行的 numpy 例子
本示例只需 numpy(numpy.linalg 已提供 matrix_rank、eigh、solve),无需额外安装。
import numpy as np
# ---------- 1. 构造关联矩阵 A(行 = 边,列 = 节点)----------
# 边表 (起点, 终点);节点用 0..3 表示 1..4
edges = [(0, 1), # e1 : 1 -> 2
(1, 2), # e2 : 2 -> 3
(3, 0), # e3 : 4 -> 1
(1, 3), # e4 : 2 -> 4
(3, 2)] # e5 : 4 -> 3
n_nodes, n_edges = 4, len(edges)
A = np.zeros((n_edges, n_nodes)) # m x n
for i, (p, q) in enumerate(edges):
A[i, p] = -1.0 # 起点 -1
A[i, q] = +1.0 # 终点 +1
print("A (m x n) =")
print(A)
print("每行之和:", A.sum(axis=1)) # 应全为 0
print("每列之和:", A.sum(axis=0)) # 也应全为 0
print("每行非零元个数:", (A != 0).sum(axis=1)) # 应全为 2
# ---------- 2. 秩:连通图应为 n - 1 = 3 ----------
r = np.linalg.matrix_rank(A)
print("rank(A) =", r, " 期望 3")
# ---------- 3. 验证 L = A^T A 就是 D - W ----------
L = A.T @ A
print("L = A^T A =")
print(L)
degrees = (A != 0).sum(axis=0).astype(float) # 每个节点的度数
Ad = (A != 0).astype(float) # 0-1 关联矩阵
W = Ad.T @ Ad
np.fill_diagonal(W, 0) # 邻接矩阵
D = np.diag(degrees)
print("度数列:", degrees, " 对角元:", np.diag(L))
assert np.allclose(np.diag(L), degrees) # 对角元 = 度数
assert np.allclose(L, D - W) # L = D - W
assert np.allclose(L, L.T) # 对称
assert np.allclose(L.sum(axis=1), 0) # 每行和为 0
# ---------- 4. 特征值:零特征值个数 = 连通分量数 ----------
w, V = np.linalg.eigh(L) # 实对称,用 eigh
print("L 的特征值(升序):", np.round(w, 6))
n_comp = int(np.sum(np.abs(w) < 1e-10))
print("零特征值个数:", n_comp, " 期望 1(连通分量数)")
print("trace(L) =", np.trace(L), " sum(lambda) =", w.sum(), " 2m =", 2 * n_edges)
print("特征多项式系数:", np.round(np.poly(w), 10)) # lambda(lambda-2)(lambda-4)^2
print("lambda_2 =", w[1], " (代数连通度)")
print("Fiedler 向量 v2 =", np.round(V[:, 1], 4)) # 正负号即二分提示
# 生成树个数:矩阵-树定理的两种算法
print("cofactor det =", round(np.linalg.det(L[1:, 1:]), 6),
" prod(lambda)/n =", round(np.prod(w[1:]) / n_nodes, 6))
# ---------- 5. 四个子空间的维数自查(秩-零化度定理) ----------
print("dim N(A) =", n_nodes - r, " (电势加常数的自由度 = 连通分量数)")
print("dim N(A^T) =", n_edges - r, " (KCL 的环流维度 = 独立回路数)")
print("欧拉公式检验: n - m + loops =", n_nodes - n_edges + (n_edges - r), " 期望 1")
# ---------- 6. 解一次电路方程 A^T A x = f,节点 4 接地 ----------
# f 为“净注入”向量:节点 1 注入 4,节点 2 抽出 3,节点 3 抽出 1
f = np.array([4.0, -3.0, -1.0, 0.0])
assert abs(f.sum()) < 1e-12 # 注入总和必须为 0
Lg = L[:-1, :-1] # 接地:删掉节点 4 的行与列
x = np.append(np.linalg.solve(Lg, f[:-1]), 0.0)
print("节点电势 x =", x)
print("KCL 残差 A^T A x - f =", np.round(L @ x - f, 12))
e = A @ x # 边落差 = 终点减起点
y = e # C = I 时的边电流
print("边落差 e =", e)
print("边电流 y =", y)
print("A^T y - f =", np.round(A.T @ y - f, 12), " (应为 0)")
print("总功耗 sum(y^2) =", y @ y, " 应等于 f^T x =", f @ x)
运行结果的要点(与 5.2 节例题的手算完全一致):
rank(A) = 3,每行之和、每列之和都为 ,每行恰两个非零元;L的对角元 与度数吻合,L == D - W成立,对称且每行和为 ;- 特征值为 ,特征多项式 ;零特征值 个 ⟹ 连通分量数 ;
- ,Fiedler 向量 ,把节点分成 与 ;
- 生成树个数: 与 都等于 ;
- 欧拉公式检验 ;
- 子空间维数:(对应"电势加常数"这一个自由度,其维数 连通分量数 )、(KCL 的环流空间 = 独立回路数);
- 电路方程解出 ,, 残差为 ,功耗 。
想算最小生成树怎么办
numpy 没有图算法。需要最小生成树时用
scipy.sparse.csgraph.minimum_spanning_tree,需要先安装:pip install scipy。它接收 的稀疏"邻接权重矩阵"(W[i,j]为边权, 表示无边),返回最小生成树的稀疏表示;若图不连通则返回最小生成森林。这正是"生成树 = 关联矩阵满秩列子集"结论的现成工具。
五、例题
例题 10.1.A:三角形图的全套计算
题目 三角形图:节点 ,边 、、。求 、、四个基本子空间的基与维数、 及其特征值。
解
第一步:写 (,行 = 边)
第二步:秩。 三行之和为零行(,,),故 ;前两行线性无关(第 3 列分别是 与 ),故 ✓(连通)。
第三步:(节点空间,维数 )。 解 :
基为 :电势整体加常数。
第四步:(边空间,维数 )。 解 (每个节点净流入为零):
基为 :沿 绕一圈,唯一的独立回路( ✓)。
第五步: 与 。 (节点空间)取 的前两行,维数 ,是"可用注入模式"(满足 );(边空间)取 的前两列,维数 ,是"可用落差模式"(满足 ,正是 KVL:绕一圈代数和为零)。
第六步:
对角元都是 (每个节点度数为 )✓,每行和为 ✓,且等于 ✓。
第七步:特征值。 : ✓,连通故单重。,其余两个之和为 。猜"符号交替"向量 :
故 。特征值为 (和 ✓)。生成树个数 ✓(三角形的生成树正是"删掉任意一条边"得到的 棵树)。这是一类规律: 的拉普拉斯特征值是 与 ( 重); 边圈 的特征值是 。
例题 10.1.B:解一个电阻网络(完整不跳步)
题目 用本篇 1.2 节那张 节点 边的图:每条边一个 电阻(故 )。在节点 1 注入 A,节点 2 抽出 A,节点 3 抽出 A,节点 4 接地()。求各节点电势、各边电流、总功耗,并验证 KCL 与功率守恒。
解
第一步:写清口径与可解性。 取 为净注入向量:
方程是 ,其中(3.6 节已算)
第二步:接地降阶。 令 ,删去第 4 行与第 4 列,得 方程组:
三个方程分别对应节点 1、2、3 的 KCL(节点 4 已接地,其方程被删去)。
第三步:消元求解。 由第 1 式 。代入第 3 式:
代入第 2 式:
于是
第四步:写全解,并用未参与求解的第 4 行检验():
第五步:边落差 (第 个分量 = 边 终点的电势减起点的电势):
第六步:边电流 (单位电阻):
读物理: 表示 上的电流实际是从节点 2 流向节点 1(约定方向是 ); 表示 上电流从节点 4 流向节点 1。注入点 1 的电势被抬到全场最高(),电流从它经 、 流出,再经 回流到被抽出的节点 2、3,符合直觉。
第七步:验证 KCL()。 逐分量算:
第八步:验证功率守恒。 各边功率之和
外部注入的功率
两端都是 ,能量守恒成立,本题完成。
本题的三个可复用检查点
1. 接地后必须用未参与求解的那一行反代检验(第四步),它最容易暴露符号错误;
2. 逐分量算一遍(第七步),不要只凭"应该成立";
3. 功率守恒 (第八步)同时检查了 、、、 四处,是性价比最高的自检。
例题 10.1.C:网络流量的完整求解(国内教材「线性方程组理论的应用」,陈维新《线性代数》附录三)
题目( 节点、 路段的公路网)
某地区的公路网有 个枢纽 与 条单行路段,方向设定如下:
| 路段 | 走向 | 含义 |
|---|---|---|
| | | 路段 1 上的车流量 |
| | | 路段 2 上的车流量 |
| | | 路段 3 上的车流量 |
| | | 路段 4 上的车流量 |
| | | 路段 5 上的车流量 |
| | | 路段 6 上的车流量 |
网络图(箭头为人为约定的正方向):
```
x1 x3
(A) ----> (B) <---- (C)
^ | ^
| x6 | x4 | x5
| v |
+------- (D) -------+
```
实测各枢纽的净注入( 表示该节点净流入、 表示净流出)为
求:(1) 全部可行流量(通解);(2) 用自由未知量的非负性给出各路段流量的可行范围;
(3) 若路段 6 封闭(),流量如何变化?若再追加封闭路段 3()呢?
(4) 把 改成 会怎样?
解
第 1 步:把「每个节点流入 = 流出」写成线性方程组。
沿用本篇 1.1 节的约定(行 = 边、起点 、终点 ),关联矩阵 是 。后面要做的事情本质上是对一个 的矩阵做行化简并读出自由未知量——每一步都能与 2-2-消元法的思想 里的流程对上:
逐行核对第 2 行:路段 2 的走向是 ,所以节点 记 、节点 记 ,即 ✓。
节点净流出 = 净注入的相反数,所以方程组是 ,其中 。把 ()与右端一起写成增广矩阵:
(最后一列是 。四个方程分别对应节点 。)
逐个节点核对方程的来历(这一步绝不能省):
- 节点 :被路段 (,流出)与路段 (,流入)、路段 (,流出)连着,净流出 ,它应等于 ,即 ;
- 节点 :流入 ,流出 ,故 ;
- 节点 :流入 ,流出 ,故 ;
- 节点 :流入 ,流出 ,故 。
四行与上面的增广矩阵完全一致 ✓。
最容易错的一步就在这里
「流入 = 流出」写出来的方程是 (无外部注入时),有外部注入时右端是净注入 ;而我们列的未知量是流出,所以右端是 。
先定口径,再列方程:本篇约定 是「净注入」。本题说「 表示 净流入 」,那么 的方程就是 。
检验办法只有一个:把四个节点逐个数一遍边(上面那四条),不要凭记忆写矩阵。
第 2 步:初等行变换(把增广矩阵化成行阶梯形)。
第 1 行乘 ():
消去第 1 列():
消去第 2 列():
消去第 4 列():
最后一行全零,说明第 4 个方程是前三个的线性组合(这与「连通图 」完全一致)。故
方程组相容,有解,且有 个自由未知量。 这里的判据就是 3-3-Ax=b的完整解 里的可解性定理: 时相容。
第 3 步:求通解(特解 + 基础解系)。
把三个非零行写回方程(顺序对应节点 ):
取自由未知量 (它们对应的列没有主元,主元在第 列)。令 ,回代:
- 由 (A):;
- 由 (C):;
- 由 (B):;
- 代回 (C):。
于是得到一个特解
验证特解(代回四个原方程,逐个核对):
再求基础解系(齐次方程组 )。仍然以 为自由未知量,依次令其中一个为 、其余为 。此时方程组是
(i) 令 :由第 1 式 ;由第 2 式 ;由第 3 式 。于是
(ii) 令 :由第 1 式 ;由第 2 式 ;由第 3 式 。得
(iii) 令 :由第 1 式 ;由第 2 式 ;由第 3 式 。得
三者线性无关(它们分别在 三个坐标上呈现"单位向量"的形状),故构成基础解系,且
通解(把自由未知量记作 ,)
用一组具体数字验证通解:取 ,得
代回四个方程:
完全正确。 所以「 净流入 、 净流出 、 净流入 」这个需求,至少有 这一组可行流量。
通解的几何解释:三个自由参数 = 三个独立回路
把基础解系逐条读成"沿回路绕一圈",每条路段按其与回路方向是否一致取 或 :
| 基础解向量 | 对应回路 | 非零分量的符号 |
|---|---|---|
| | | (逆向)、、(逆向)、(逆向) |
| | | 、、 |
| | | 、、 |
每个 都满足 :"沿回路绕一圈,每个节点进多少就出多少"。这就是 3-5-四大子空间的维数 中 的物理内容——通解里三个自由参数的含义是:可以在每个独立回路上任意叠加任意大小的环流,而不破坏任何节点的流量守恒。
第 4 步:用非负性给出可行范围。
车流量不可能为负,所以要求 ()。把第 3 步的通解逐条代入:
可行域是 空间中由 个半空间围成的无界凸多面体(它有一部分是"锥形"的,因为 同时增大时 与 会变负,但沿某些方向可以无限延伸)。这说明一个重要的现实结论:仅有"节点进出总量"这一组条件,路网流量的分配方案一般有无穷多种,不是唯一的。
代入检验几个点:
| 是否可行 | ||
|---|---|---|
| ✓ 全非负 | ||
| ✓ | ||
| ✓ | ||
| ✗ :路段 1 会出现"倒流" |
注意第三个可行点的含义: 给出 、,都远大于基准方案,但四个节点的净进出完全一样。这就是"线性方程组有无穷多解"在交通规划里的现实含义:总量约束之外还有"环流自由度",要靠交通调查或一个优化目标(例如"总行驶时间最小")才能定出唯一方案。
第 5 步:情形一——路段 6 封闭(,即 )。
令 ,通解只剩两个自由未知量 :
非负约束变成
取几个可行点:
| 说明 | ||
|---|---|---|
| 与基准相比, 由 降到 , 由 降到 | ||
| 若要求 保持 ,则 ,此时 由 升到 | ||
| 路段 1 恰好被压到零 |
读出来的物理结论:路段 6 一关,原来绕 的那部分车流被挤到别的路上——封闭一条路段相当于把一个自由未知量固定为 ,解集从三维降到二维。这与"删掉 的一列, 的维数减少 "是同一件事。
第 6 步:情形二——再追加封闭路段 3(,即 )。
此时 ,通解只剩一个自由未知量:
若还要求 保持 ,则 ,得到唯一解
检验: ✓; ✓; ✓; ✓。
这正是「生成树」的情形:剩下的路段 中路段 是唯一的"冗余"边,而它已被固定为 ,于是流量被节点的流入流出条件完全确定。
封闭路段与自由度的对应关系(本题的核心规律)
设网络有 个节点、 条路段、 个连通分量,则
每封闭一条路段, 减 ,自由度最多减 ;当剩下的路段恰好构成生成树()时,自由度变成 ,流量被唯一确定。
本题:,,,自由度 ;封闭路段 6 后 ,自由度 ;再封闭路段 3 后 ,自由度 ;若再把路段 2 也封掉(),自由度 ,即唯一解。
这个规律正是第 3.8 节「生成树 = 关联矩阵中线性无关的 列」那句话的来源(下面例题 10.1.F 会证明它)。
第 7 步:情形三——把 改成 ,为什么无解?
原来的 ,四个分量之和为 。若把 改成 ,则
计算两个秩:
由线性方程组理论(3-3-Ax=b的完整解 的可解性判据),方程组无解。
为什么必然无解(一句话的本质):(连通图,见 1.4 节),而" 有解"要求 与 正交,即
上式不为零,于是无解。 物理含义: 就是 2.4 节的电荷守恒 / 流量总量守恒——注进去的总量必须等于抽出来的总量。 从 改成 ,相当于"多抽走了 个单位却没人补上",任何路段分配都无法弥补这个总量缺口。
数值确认:用最小二乘求"最接近的解",残差向量是
残差在每个节点上完全相等——这个漂亮的对称性说明:最优的"妥协方案"是把 个单位的缺口平均分摊到四个节点上(每个节点差 )。这也从数值上印证了"缺口是全局性的,不是某一个节点的问题"。
再补充一个"封闭路段导致无解"的例子(更贴近工程):若封闭路段 1(),则节点 被孤立,此时节点 的方程退化为
只有当 时才可能成立。 题设 ,所以封闭路段 1 之后方程组立即无解——这就是 3-3-Ax=b的完整解 里 的图论版本:"某个连通分量的净注入必须为零",否则该分量内部无法守恒。
本题的三条可复用套路
1. 列方程前先定口径:把"流入 = 流出"统一写成 ( 是净注入),或统一写成 ( 是流出)。全篇一致就不会错。
2. 先算两个秩: 与 。相等 ⟹ 有解,自由度为 ;不等 ⟹ 无解,且无解的原因必定是"总量条件(割条件)不满足"。
3. 非负性分析用自由未知量写:把每个 都写成自由未知量的表达式,再逐条写 ,得到的就是"各路段流量的可行范围"。
这一类问题的统一性(陈维新教材的原始出发点)
灌溉网、电力网、物资流通网、通信网、交通网的流量计算,全都归结为解同一个线性方程组
其中 是网络的关联矩阵、 是各管段/线路/路段上的流量、 是各节点的净注入(水源注入、电厂出力、仓库进货、总站收发量……)。物理背景不同,方程的形状完全相同——这正是线性代数作为"通用语言"的价值。具体对应见下一小节 6.6。
六、应用
6.1 电路分析(circuit analysis)
这是关联矩阵的"母语场景"。 个节点、 条支路的电路,其节点法(nodal analysis)方程正是
- 未知量 = 各节点电势;
- 系数矩阵 = 电路的节点导纳矩阵(admittance matrix),也就是加权拉普拉斯矩阵 ;
- 右端 = 各节点注入的电流源。
工程软件(SPICE 类)的核心就是解这个方程组。它是稀疏的(每个节点只与少数几条边相连),接地后是对称正定的,因此可用稀疏 Cholesky、共轭梯度或预处理迭代法高效求解——这正是第 11 章 11-3-迭代方法与预条件 的典型场景。接地与可解性的两个结论(定理 10.1.4、)就是仿真软件里"必须接地"与"电流源必须成对出现"的数学根据。
6.2 社交网络与网络中心性
把社交网络看成图:节点是人,边是"关注/好友"关系。于是:
- 度数中心性(degree centrality): 的对角元就是度数,最简单的影响力指标;
- 特征向量中心性(eigenvector centrality):用邻接矩阵 ( 表示相连,对称 - 矩阵)的最大特征值对应的特征向量。直观上"重要的人连接着重要的人",写成方程就是 ;
- 谱聚类(spectral clustering):用 Fiedler 向量( 对应的特征向量)的正负号把网络切成两块,或用前几个特征向量做嵌入。图的"分块结构"直接写在 的谱里:若网络由两个几乎不相连的簇组成,则 非常接近 ,对应特征向量在簇内近似常数、在簇间跳变。
一句话记法: 的零特征值个数 = 硬簇个数(完全不连); 的大小 = 最松的那一刀有多难切(软簇结构)。
6.3 PageRank 的图基础
把网页看成节点、超链接看成有向边,就得到一个规模以十亿计的有向图。PageRank 的想法是:在这个图上做一个"随机冲浪者"的 Markov 链,其稳态分布就是网页的重要性排名。
- 从关联结构到转移矩阵:设节点 有 条出边,则从 沿每条出边走的概率为 。按"从 到 "的列存法写出随机矩阵(Markov matrix)(每列和为 ): 若 有边;
- 稳态分布 满足 ,即特征值 的特征向量;
- 网络图的病态之处:悬挂节点(dangling node,没有出边的网页)会让某一列为全零,矩阵不再是随机矩阵;周期性(例如纯粹的双向对链)会让迭代不收敛。PageRank 的修补办法是引入阻尼因子(damping factor)(通常 ):
它保证 是正矩阵(所有元素 ),从而由 Perron–Frobenius 定理有唯一稳态且幂迭代必收敛。
这就是为什么"应用"这一章要放在特征值与 SVD 之后:它把四大子空间、特征值、马尔可夫链一次性用在一个真实的大规模问题上。完整展开见 10-2-Markov矩阵与稳态。
6.4 其他场景速览
- 交通与物流网络:节点是路口/仓库,边是道路。车流分配是 (流量守恒)的实例;最小生成树决定"最省钱的连通方案";最短路决定路径规划。
- 图像处理:像素是节点、相邻像素连边, 就是图像的离散拉普拉斯算子,用于去噪、分割与图割(graph cut)。 度量图像的总变差("不平滑程度")。
- 有限元与偏微分方程:把连续区域离散成网格(图),刚度矩阵正是加权拉普拉斯矩阵。"" 在图上就是 ""——这是本篇与微分方程数值解的交汇点。
- 化学分子结构与生物网络(蛋白质相互作用、基因调控):都用 的谱提取结构信息。
6.5 工程中的矩阵:弹簧-质点系统与刚度矩阵
这是本篇与 Strang §10.2 的接口
同一套 在电路里给出节点导纳矩阵,在弹簧-质点系统里给出刚度矩阵(stiffness matrix),在图里(取 )给出拉普拉斯矩阵。
物理不同,矩阵同形——这正是线性代数作为"通用语言"的体现。
建模。 把 个质点串在一条线上,相邻质点(以及两端与墙)之间用弹簧连接。记:
- 为各质点的位移(沿轴向,);
- 为各弹簧的伸长量();
- 为各弹簧的内力();
- 为施加在各质点上的外力()。
三块结构拼起来:
| 关系 | 表达式 | 名称 | 说明 |
|---|---|---|---|
| 几何关系 | 伸长量 = 位移之差 | 是关联矩阵(行 = 弹簧,列 = 质点),相邻取 | |
| 本构关系 | 胡克定律 | , 是弹簧刚度 | |
| 平衡关系 | 节点力平衡 | 每根弹簧的内力按方向分给两端质点 |
把三者串起来:
就是刚度矩阵。
性质。 是对角正定矩阵(弹簧刚度为正),故
右边正是弹簧的弹性势能的两倍——所以 半正定,且零空间恰好对应"整体刚体运动"(各质点位移相同则所有弹簧都不伸长,)。两端固定(给定位移约束)后零空间消失, 变为正定,系统有唯一平衡解。
一个完整的数值例子。 取 个质点、 根弹簧(两端接墙),刚度全为 :
对称正定(特征值约 、、)。只在中间质点施加拉力 :
结果完全符合物理直觉:中间质点位移最大(),两端因靠近固定墙而位移减半(),且左右对称。
与图拉普拉斯矩阵的关系
取 (所有弹簧刚度相同),立刻得到 ——
这正是本篇前面反复使用的图拉普拉斯矩阵(第 4 节)。
所以"电路的网络矩阵""弹簧系统的刚度矩阵""图的拉普拉斯矩阵"是同一个 ,差别只在 的取值与物理含义。
位移类比电势、内力类比电流、外力类比注入电流,### 6.6 网络流量:灌溉网、电力网、物资流通网的统一模型(国内教材补充)
一句话
所有"守恒型"网络的计算,最后都归结为解同一个线性方程组 。
模型的统一写法。 设网络有 个节点、 条边(管段 / 线路 / 路段), 是 关联矩阵, 是各边上的"流量"(沿约定正方向为正), 是各节点的"净注入"。"每个节点流入 = 流出"就是
把四类网络逐项翻译一遍(这是本节最值得抄下来的一张表):
| 网络 | 节点 | 边 | 边上的量 | 节点净注入 | 守恒律的物理名称 |
|---|---|---|---|---|---|
| 灌溉网(渠道、管网) | 分水口、汇流点 | 渠道 / 管段 | 流量() | 水源供水量(正)/田间取水量(负) | 水量守恒 |
| 电力网 | 变电站、母线 | 输电线路 | 有功功率(MW) | 发电机出力(正)/负荷(负) | 功率平衡(KCL) |
| 物资流通网 | 仓库、配送中心 | 运输线路 | 运量(t) | 进货量(正)/发货量(负) | 物资守恒 |
| 交通网 | 路口、枢纽 | 路段 | 车流量(辆/h) | 驶入量(正)/驶出量(负) | 车流守恒 |
| 电路网络(本篇 3.5 节) | 节点 | 支路 | 电流(A) | 电流源注入 | 基尔霍夫电流定律 |
四个必问的问题(解任何网络流量问题的标准流程):
- 有没有解? 判据是 。对本篇约定( 是 关联矩阵):
- 图连通时,,所以"有解"等价于 (总量守恒);
- 图不连通时,还要每个连通分量各自满足 (每个"孤岛"内部也要守恒)。
- 有多少解? 自由度 ,就是独立回路数。自由度 意味着"总可以沿回路叠加环流"。
- 哪些解是物理可行的? 加上非负性 (或上下界 ,即容量约束)。把通解代进去逐条写不等式,就得到可行范围。
- 改变条件会怎样? 封闭路段 = 删掉一列, 减 ;若删列使图不连通,则还要检查被孤立的连通分量的净注入是否为 ,否则无解( 与 不再相等)。
三个"变难"的方向(把线性方程组升级为线性规划)
1. 加容量上界 :解集从"仿射子空间"变成多面体,求"最大输送量"就变成线性规划(见 10-3-线性规划,最大流—最小割定理就是它的对偶定理);
2. 加费用(每条路段单位流量成本 ):求 ,这就是最小费用流;
3. 加损耗(流量在传输中按比例损失):守恒方程变成 的非线性版本,需要迭代求解——但线性方程组的解仍然是每一次迭代的核心步骤。
一句话:线性方程组给出"可行方案空间",线性规划在它上面挑"最优方案"。先会解方程,再谈优化。
与最小生成树的接口
生成树的"正确性证书"也是线性的: 是生成树 且 的列线性无关(例题 10.1.F)。
于是"在不超过预算的前提下把 个节点连通"变成"在关联矩阵的满秩 列子集中找权重最小者"——这是一个纯线性代数的选择问题,Kruskal 算法只是它的贪心解法。
注意区分两个"最小":最小生成树是"连通所有节点、总造价最小"(树,无回路);最短路是"两点间路程最短"(可能绕路,不必是树)。两者都用 表述,但目标函数不同。
数值示例(加入容量约束后的"可行性"检查):回到例题 10.1.C 的网络,若每段路的通行能力上限是 ,那么 给出的 超容,不可行;而 给出的 全部不超过 ,可行。把非负性换成 后,"可行范围"就从一个无界多面体变成了有界多胞体——这已经是线性规划的雏形了(见 10-3-线性规划)。
七、易错点
本篇八个高频错误
1. 形状搞反: 是 (行 = 边)还是 (列 = 边)?本库统一 (行 = 边),因此三条定律写成 、、。看到别人的公式长相不同时,第一件事是确认他的 是几行几列——两种约定互为转置,所有公式( 还是 )都会互换。
2. 维数公式套错对象:(节点侧、加常数);(边侧、回路)。搞混的后果是"把电势加常数说成回路",一句话错两处。
3. 把两个"零空间"当成同一个:(维数 ,电势加常数)与 (维数 ,独立回路)所在空间与物理含义完全不同。连通图时二者恰好都是一维,极易混淆。判断方法永远是:看向量有几个分量。
4. 手写 写错:对角元是度数、非对角元在"相连"时为 、不相连时为 (最容易把不相连写成 )。四条检查:、第 行非对角非零元个数 、、用程序验
L == A.T @ A。5. 忘记接地: 一定奇异(),直接解 得到的是"差一个常数"的解族。必须指定参考节点(删一行一列)才有唯一解。反过来,若 ,无论怎么接地都无解(电荷不守恒)。
6. 把"看得见的圈"当成"独立回路":平面图上目测能数出很多圈,但独立回路只有 个。本篇例子中"两个三角形 + 一个外圈"共 个圈,独立回路数是 (外圈 两个三角形之差)。判据:。
7. 忘记自定义方向的影响:无向图的方向是人为选的,换方向相当于给 的某一行乘 。这不改变任何维数与秩,但会改变具体向量(回路、电流、落差)的分量正负号。答题时先声明方向约定,答案都相对该约定。
8. 把"净流入"与"净流出"混用:在"起点 、终点 "的约定下, 是净流入。若题目给的是"抽出多少安",符号要与"注入"口径统一(抽出 = 负注入)。做题第一步永远是写清 的口径,并在最后用功率守恒复核一次。
八、练习题
练习 10.1.1(基础)
对路径图 :节点 ,边 、、。写出 的关联矩阵 ,求 、、,写出四个基本子空间的基,并验证欧拉公式。
练习 10.1.2(基础)
对 节点 边的圈图 (),求 与它的全部特征值。用矩阵—树定理 算出生成树个数,再"目测"独立数一遍,看是否一致。
练习 10.1.3(进阶)
接练习 10.1.1 的路径图 ,在节点 1 注入 A、节点 4 抽出 A(其余节点无注入),所有边电阻为 。写出 ,接地节点 4,解出各节点电势与各边电流。用功率守恒 检验答案,并解释为什么电势沿路径线性下降(提示:这是"离散拉普拉斯方程" 的差分版本)。
练习 10.1.4(进阶)
证明:对任意图,( 为连通分量数)。要求:不可以直接引用"",而要自己从二次型 出发,配合连通性给出完整证明。
练习 10.1.5(思考)
设 连通, 是关联矩阵。证明""与"沿 的每个回路, 的分量按圈方向取正负后代数和为零"等价(这就是 KVL 的两种表述)。再在例题 10.1.A 的三角形图上举一个 的具体例子,并说明它在物理上意味着什么。
更多易错点(网络流量专题,承接第七节)
网络流量计算的六个专属陷阱
1. 把"净流入"当成"总流入"。 节点方程里的 是净注入(流入减流出),不是流入总量。若题目说" 点驶入 辆、驶出 辆",那么 ,而不是 。
2. 忘记"总量的和必须为零"先做一次检查。 动手解方程组之前,先算 。它不为零就直接写"无解",可以省下大量消元时间。这一步在考试里能救命。
3. 把"封闭路段导致无解"和"封闭路段导致解不唯一"搞混。 两者的判据完全不同:
- 无解:封闭后 。典型原因是被孤立的连通分量净注入不为零;
- 解不唯一:封闭后仍然 ,但自由度 。
前者是"条件被破坏",后者是"条件不够强"。先看秩,再谈解。
4. 自由未知量取错,导致"基础解系"不是回路。 基础解系可以任意取(任何一组基都行),但取成"每个独立回路一个向量"时物理意义最清楚。反过来,若你算出的基础解系不是回路形状(有 、 之类的系数),先检查是不是行化简时漏了主元——回路向量中非零分量的系数一定只能是 (因为回路每条边只走一次)。
5. 用"看得见的圈"去数自由度。 和 2.3 节一样,图上目测能看到很多圈,但自由度只有 个。判据永远是秩,不是眼睛。
6. 把 与 的方向搞反,导致"行数 = 节点数"与"列数 = 节点数"混用。 本篇统一 是 (行 = 边),所以节点方程是 ( 个方程)。若你写成 ,方程个数就变成 个,物理含义完全不同(那是"每条边一个方程",不是守恒律)。
补充练习(网络流量,配合第八节)
补充练习 10.1.6(基础) 对例题 10.1.C 的网络,若把路段 4()方向反过来(改成 ),关联矩阵怎样变化?四个节点的方程怎样变化?通解中的基础解系是否改变?要求:重新写出增广矩阵并做一次完整行化简,比较自由度是否改变。
补充练习 10.1.7(进阶) 某灌溉网有 个节点、 条渠道,节点净注入为 。
(1) 验证 ;
(2) 若网络连通,求自由度数;
(3) 若封闭一条渠道后渠道 3 恰好把节点 孤立,而 ,说明此时方程组无解,并写出两个秩;
(4) 若把 改成 、同时把 从 改成 ,方程组的可解性如何变化?
补充练习 10.1.8(进阶,与最小生成树接口) 对例题 10.1.C 的网络,六条路段的造价为 。
(1) 用 Kruskal 算法手算最小生成树(按造价从小到大加边,成圈则丢弃),写出每一步;
(2) 验证最小生成树的 条边对应的关联矩阵列线性无关;
(3) 说明"最小生成树"与"独立回路数 "的关系(提示:生成树的补边数恰好等于独立回路数)。
补充练习 10.1.9(思考) 证明:若网络连通且 、 都是 的可行解(即满足非负性的解),则 必是若干回路的组合。要求:利用 与"回路空间"的对应关系,说明"两个可行方案的差别只能是环流"这一物理结论。
九、常见问题 FAQ
Q1:为什么本库用"行 = 边"的 ,而有的资料用"列 = 边"?
因为要让 成为 的节点矩阵()。若把关联矩阵写成 (列 = 边),则 是 的边矩阵,节点拉普拉斯变成 。这不是"谁对谁错",而是两种互为转置的约定:Strang 教材与 MIT 18.06 第 12 讲采用本篇这种( 是他们那一讲的招牌结论)。读任何资料前先确认形状,这比记公式重要得多。
Q2: 为什么叫"独立回路数"?
拿一支笔从任意节点沿边做树状扩展,扩到所有节点为止,用掉 条边(构成生成树)。剩下的 条边(弦)每条都能与树上唯一路径合成一个圈,而且这些圈互相独立(每条弦只属于自己那个圈)。所以独立回路数 。它与 是同一个数——"回路"与"零空间向量"在图上是同一件事的两种语言。
Q3:拉普拉斯矩阵的特征值到底"看"的是什么?
三个层次:(1) 零特征值的个数看连通分量数(硬结构);(2) 最小非零特征值 看"最容易切的那一刀有多难切"(连通强度/聚类质量);(3) 整个谱给出图的嵌入坐标(谱嵌入),可用于可视化与聚类。物理上把图当电阻网络: 越大,任意两点间的有效电阻越小,电流越容易流遍全图。
Q4:这一章和 SVD、最小二乘有什么关系?
关系很深: 正是最小二乘正规方程的系数矩阵(见 4-3-最小二乘逼近),而电路方程 用的是同一个结构; 是对称半正定矩阵,它的谱分解 是 6-4-对称矩阵与正定矩阵 的标准例子;谱聚类要用 的特征向量做嵌入,与 SVD 的低秩逼近思想一致(见 7-1-SVD的构造与几何意义)。一个关联矩阵的两条路: 的四大子空间(本章) 的谱(聚类与嵌入)。
本篇小结
一、核心结论(十句话)
- 图可以写成矩阵:关联矩阵 (,行 = 边、起点 、终点 )把组合信息变成线性代数对象。
- 是差分算子(节点 → 边,取落差), 是散度算子(边 → 节点,求和)。判断"用 还是 "只需问:这一步的输入住在哪个空间?
- 秩:;连通图()时 。
- (节点空间,维数 ):电势可以整体加常数;连通时 。
- (边空间,维数 ):独立回路(环流)——"看得见的圈"多于"独立回路",判据永远是秩。
- 秩—零化度定理在图上的形态就是欧拉公式:。
- 三条物理定律三个矩阵等式:(KVL)、(欧姆)、(KCL),串起来得 ,其中 是拉普拉斯矩阵。
- 拉普拉斯矩阵的五条性质:对称、半正定( 即离散 Dirichlet 能量 / 总功耗)、行和为 、零特征值个数 = 连通分量数、谱给出去噪 / 聚类 / 嵌入的信息。
- 网络流量统一模型:。有解 ⟺ ⟺ 每个连通分量的净注入为零;自由度 = = 独立回路数;加非负性 即得可行范围。灌溉网、电力网、物资流通网、交通网全部归结为解同一个线性方程组。
- 生成树 关联矩阵的 个线性无关列,于是最小生成树 = "在满秩 列子集中挑权重最小者"——组合优化被翻译成线性代数。
二、易混概念对照表
| 容易混淆的一对 | 它们分别是什么 | 一句话区分 |
|---|---|---|
| 与 | 维数 (电势加常数)vs 维数 (回路) | 看向量有几个分量: 个分量的在节点空间, 个分量的在边空间 |
| 与 | (电势平移)vs (均匀环流) | 数一数 有几项就知道它在哪个空间 |
| 回路空间 与割空间 | 边空间里的环流 vs 节点空间里的注入 | 一个是 维、一个是 维 |
| 独立回路数 与 目测圈数 | vs 图上看得见的圈 | 外圈往往是三角形的组合,不独立 |
| KCL 的"净注入"与"净流出" | vs | 口径要全篇一致;物理内容相同 |
| 与 | 无权拉普拉斯 vs 加权拉普拉斯 | 时后者退化成前者 |
| 电路的节点法 与 弹簧的刚度矩阵 | 物理不同、矩阵同形: 是电导 / 弹簧刚度 | |
| "有解"与"非负可行" | vs 再加 | 有解只保证存在实数解,非负性是额外的物理约束 |
| "封闭路段后无解"与"封闭路段后解变多" | vs 自由度 | 前者条件被破坏,后者条件不够强 |
| 生成树 与 最短路 | 连通全部节点的最小造价子图 vs 两点间最短路径 | 前者是树(无回路),后者一般不是树 |
| 与 | 两个不同的矩阵、两个不同的空间 | 恰好数值相同,因为都由"边两端相等"刻画——但不要因此以为它们是一个东西 |
三、三句话记住全篇
用一张卡片背下本篇:
- 节点侧: 管"电势加常数", 管"可实现的注入()";
- 边侧: 管"可实现的落差(沿回路代数和为零 = KVL)", 管"回路";
- :把两侧缝在一起,得到对称、稀疏、半正定的拉普拉斯矩阵。
相关笔记
- 3-5-四大子空间的维数 —— 本篇的图论内容就是四大子空间的一次实物解剖: 是"行秩 = 列秩"的另一张面孔
- 4-1-四大子空间的正交性 —— 的物理化身就是基尔霍夫电压定律
- 4-3-最小二乘逼近 —— 法方程 与电路方程 共用同一个矩阵
- 6-4-对称矩阵与正定矩阵 —— 拉普拉斯矩阵是对称半正定矩阵的教科书例子
- 10-2-Markov矩阵与稳态 —— 有向图的转移矩阵与稳态分布,PageRank 的完整展开
- 11-3-迭代方法与预条件 —— 大规模稀疏拉普拉斯系统的求解方法
参考来源
- MIT 18.06 Linear Algebra, Lecture 12: Graphs, networks, incidence matrices:<https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-12-graphs-networks-incidence-matrices/>
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016(第 10.1 节 Graphs and Networks;):<https://math.mit.edu/~gs/linearalgebra/>
- NumPy 官方文档
numpy.linalg.matrix_rank:<https://numpy.org/doc/stable/reference/generated/numpy.linalg.matrix_rank.html> - NumPy 官方文档
numpy.linalg.eigh:<https://numpy.org/doc/stable/reference/generated/numpy.linalg.eigh.html> - SciPy 官方文档
scipy.sparse.csgraph.minimum_spanning_tree:<https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html> - 同济大学数学系《线性代数》第六版,高等教育出版社(第四章「向量组的线性相关性」「线性方程组解的结构」、第五章「相似矩阵及二次型」为对照章节)