w wyl123ly 的博客
MD

10-1-图与网络

106 KB 2026.10.11 原文件

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)。

凭图的形状"顺手写 "是最常见的错误来源——尤其容易把"不相连"误写成 。

性质清单(五条,每条给理由)

  1. 对称:( 对角故对称)。适用条件: 对称。
  2. 半正定(positive semidefinite):对任意 ,

把 展开(它就是边 的落差 ):

(求和号下的 "edges " 表示"对一切边 求和"。)

物理解释:这正是电路的总功耗。 数学解释:它是"离散 Dirichlet 能量",度量 在图上有多不平滑。

  1. 每行和为 (等价地 ):由闭式,第 行和 。故 , 一定奇异()。这与"电势可整体加常数"是同一件事: 里 只以差值出现。
  2. 连通分量数 :由第 2 条的展开式, 当且仅当每条边两端相等;由定理 10.1.1 证明中的同一论证,这当且仅当 在每个连通分量上取常数。这些向量恰构成 ,故

注意:这里 与 维数相同、物理含义相同(都是"每个连通分量内加常数"),因为二者都由"边两端相等"这一条件刻画。(这与 2.3 节的 完全不同——后者的向量住在 ,是回路。)

  1. 特征值非负实数:由第 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):在连通图中选 条边把所有节点连起来、总权重最小。它的线性代数含义有两层:
  1. 生成树 = 关联矩阵中线性无关的 列。因为 ,任取 列若线性无关,就确定一棵包含所有节点的树;多余的列必是这些列的线性组合。于是"最小生成树 = 在 的所有满秩 列子集中找权重最小的一组"——组合优化被翻译成了线性代数。
  2. 树上 :树上没有回路,维数 ✓。

经典算法是 Kruskal 贪心:按权重从小到大加边,若成圈则丢弃。用 scipy 可一行计算(见 4.4 节)。

  • 最短路径(shortest path):把边看成电阻,则两点间等值电阻 = 在 间注入单位电流时两点的电势差:

其中 是 Moore–Penrose 广义逆。这把"电阻网络的有效电阻"与"随机游走的首次命中时间"联系起来,是图嵌入(graph embedding)与半监督学习的基础。

  • 网络流(network flow):最大流问题写成线性规划,约束矩阵正是关联矩阵:流量守恒 与容量约束 。最大流—最小割定理(max-flow min-cut theorem)是线性规划对偶定理的特例——这把图论、线性代数与第 10.3 节的线性规划连成一条线。

四、计算方法与步骤

4.1 构造关联矩阵的标准流程

  1. 给节点编号 ,给边编号 (顺序任意,但要记下来);
  2. 给每条无向边人为指定方向并写下边表(例如"");
  3. 开一个 的零矩阵(行 = 边,列 = 节点),逐行填:第 条边 ,则位置 填 、 填 ;
  4. 自查:每行恰好两个非零元、行和为 ;每列和也为 ;若某行全零,说明漏了方向(自环除外);
  5. 顺手记下度数列 ,用于交叉验证 。

4.2 求四个基本子空间的基(图上的专用写法)

记 为节点数、 为边数、 为连通分量数、。

  1. 秩:;连通时 。数 用并查集或广度优先搜索。
  2. (节点空间,维数 ):对每个连通分量取"该分量上全 、其余为 "的向量。连通图时就是 。
  3. (边空间,维数 ):先求一棵生成树,对每条弦 找出树上 的唯一路径,"弦 + 路径"组成圈,沿圈定向给每条边赋 。
  4. (节点空间,维数 ):取 的 个线性无关列即得基,等价于取 的 个线性无关行。物理上它是"可用注入模式",且每个基向量都与 正交。
  5. (边空间,维数 ):取 的 个线性无关列即得基,即"可用落差模式";由定理 10.1.5,它恰是"与所有回路正交"的落差全体。

4.3 解电路方程

  1. 接地:选定参考节点 ,令 ,删去系数矩阵的第 行与第 列(得到 可逆矩阵,定理 10.1.4);
  2. 可解性检查:(电荷守恒),否则无解——这是 3-3-Ax=b的完整解 可解性条件在图上的化身;
  3. 解线性方程组得 ;
  4. 回代 得边落差(终点减起点);
  5. 回代 得边电流;
  6. 自检:(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. 有没有解? 判据是 。对本篇约定( 是 关联矩阵):
  • 图连通时,,所以"有解"等价于 (总量守恒);
  • 图不连通时,还要每个连通分量各自满足 (每个"孤岛"内部也要守恒)。
  1. 有多少解? 自由度 ,就是独立回路数。自由度 意味着"总可以沿回路叠加环流"。
  2. 哪些解是物理可行的? 加上非负性 (或上下界 ,即容量约束)。把通解代进去逐条写不等式,就得到可行范围。
  3. 改变条件会怎样? 封闭路段 = 删掉一列, 减 ;若删列使图不连通,则还要检查被孤立的连通分量的净注入是否为 ,否则无解( 与 不再相等)。

三个"变难"的方向(把线性方程组升级为线性规划)

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的构造与几何意义)。一个关联矩阵的两条路: 的四大子空间(本章) 的谱(聚类与嵌入)。


本篇小结

一、核心结论(十句话)

  1. 图可以写成矩阵:关联矩阵 (,行 = 边、起点 、终点 )把组合信息变成线性代数对象。
  2. 是差分算子(节点 → 边,取落差), 是散度算子(边 → 节点,求和)。判断"用 还是 "只需问:这一步的输入住在哪个空间?
  3. 秩:;连通图()时 。
  4. (节点空间,维数 ):电势可以整体加常数;连通时 。
  5. (边空间,维数 ):独立回路(环流)——"看得见的圈"多于"独立回路",判据永远是秩。
  6. 秩—零化度定理在图上的形态就是欧拉公式:。
  7. 三条物理定律三个矩阵等式:(KVL)、(欧姆)、(KCL),串起来得 ,其中 是拉普拉斯矩阵。
  8. 拉普拉斯矩阵的五条性质:对称、半正定( 即离散 Dirichlet 能量 / 总功耗)、行和为 、零特征值个数 = 连通分量数、谱给出去噪 / 聚类 / 嵌入的信息。
  9. 网络流量统一模型:。有解 ⟺ ⟺ 每个连通分量的净注入为零;自由度 = = 独立回路数;加非负性 即得可行范围。灌溉网、电力网、物资流通网、交通网全部归结为解同一个线性方程组。
  10. 生成树 关联矩阵的 个线性无关列,于是最小生成树 = "在满秩 列子集中挑权重最小者"——组合优化被翻译成线性代数。

二、易混概念对照表

容易混淆的一对它们分别是什么一句话区分
与 维数 (电势加常数)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>
  • 同济大学数学系《线性代数》第六版,高等教育出版社(第四章「向量组的线性相关性」「线性方程组解的结构」、第五章「相似矩阵及二次型」为对照章节)