深入浅出 Kirchhoff 矩阵树定理——从电路到生成树的统一
小粉兔
·
2026-06-30 02:11:01
·
算法·理论
::::info[注意]{open}
本文是测试使用大模型辅助写作博客文章的效果的实验性文本。
虽然效果不咋地就是了，DeepSeek V4 Pro 有点憨憨，我调教了好久好久。
::::
本文是受到我于 2026 年 1 月 18 日于 Luogu Academic 群中关于等效电阻与 Kirchhoff 矩阵树定理的讨论的启发，我引导了 DeepSeek V4 Pro 补充完整逻辑、具体细节、与适当的延申讨论，并经同一模型辅助润色成文。
引言
Gustav Robert Kirchhoff 在十九世纪中叶做了两件影响深远的大事：一是提出了电路分析中普适的 Kirchhoff 电流定律（KCL）与电压定律（KVL）；二是发现了图的生成树数目与 Laplace 矩阵行列式之间的关系，即后来所称的 Kirchhoff 矩阵树定理。或许令人惊讶的是，Kirchhoff 最初正是为了计算电阻网络的等效电阻，才推导出矩阵树定理！本文将带读者从一段导线与电阻开始，逐步建立网络的图论模型，引出 Laplace 矩阵，再通过矩阵树定理与分离两点的生成森林（2-树）的巧妙概念，最终得到任意电阻网络中等效电阻的简洁行列式表达式。我们还会亲手计算一枚 Wheatstone 电桥（配置为非对称电阻值），体验公式的威力。此外，本文还会讨论广义串并联图上的快速简化算法、Y-Δ 变换，并分析其与普适行列式方法的联系与局限。希望你能通过本文，感受到图论、线性代数与电路分析三者融合的数学之美。
1. Kirchhoff 定律与节点电压方程
1.1 两大定律与 Ohm 定律
任何电阻网络的行为都由三条基本规则支配：
Kirchhoff 电流定律（KCL） ：在电路的任一节点处，流入该节点的电流之和等于流出该节点的电流之和。Kirchhoff 电压定律（KVL） ：沿电路中任一闭合回路，各元件上的电压降的代数和为零。Ohm 定律 ：对阻值为 R 的电阻，其两端的电压 V 与流过它的电流 I 满足 V = I R 。引入电导 c = \frac{1}{R} 后，也可写为 I = c V 。
这些定律是宏观电路理论的基石，下面我们将它们翻译为矩阵语言。
1.2 关联矩阵与 Laplace 矩阵
设网络有 n 个节点和 m 条电阻元件。为每条边 e 指定一个任意参考方向，并定义 n \times m 的关联矩阵 \mathbf{B} ：若边 e 从节点 u 指向节点 v ，则 \mathbf{B}_{u, e} = +1 ，\mathbf{B}_{v, e} = -1 ，其余为 0 。记 \mathbf{v} \in \mathbb{R}^n 为节点电压向量，则 \mathbf{B}^{\mathsf{T}} \mathbf{v} 是一个 m 维向量，其第 e 个分量正是边 e 两端的电压差（方向为参考方向）。
设每条边 e 的电导为 c_e > 0 ，构成对角矩阵 \mathbf{C} \in \mathbb{R}^{m \times m} ，其中 \mathbf{C}_{e, e} = c_e 。由 Ohm 定律，流过各边的电流向量为 \mathbf{i}_{\text{edge}} = \mathbf{C} \mathbf{B}^{\mathsf{T}} \mathbf{v} 。
最后应用 KCL：每个节点的净注入电流等于连接到该节点的各边电流的代数和（约定注入为正、流出为负）。用 \mathbf{i} \in \mathbb{R}^n 表示节点注入电流向量，则有 \mathbf{i} = \mathbf{B} \, \mathbf{i}_{\text{edge}} 。代入即得
\mathbf{i} = \bigl( \mathbf{B} \mathbf{C} \mathbf{B}^{\mathsf{T}} \bigr) \mathbf{v} \text{。}
可见系数矩阵完全由网络拓扑和电导决定，我们称之为 Laplace 矩阵 （又称 Kirchhoff 矩阵），记为
\mathbf{L} = \mathbf{B} \mathbf{C} \mathbf{B}^{\mathsf{T}} \text{。}
1.3 Laplace 矩阵的结构
直接展开乘积，可得 \mathbf{L} 的显式元素（i \neq j ）：
\mathbf{L}_{i, j} = -c_{i, j} \quad \text{（若 } i \text{ 与 } j \text{ 间有边，多边则求和）} \text{；}
\mathbf{L}_{i, i} = \sum_{j \neq i} c_{i, j} \text{。}
这里 c_{i, j} 表示连接节点 i 与 j 的边的电导，若无边则为 0 。\mathbf{L} 是对称矩阵，且每行（列）元素之和为 0 ：\sum_{j} \mathbf{L}_{i, j} = 0 。因此 \mathbf{L} 是奇异的，其零空间由全 1 向量 \mathbf{1} 张成：
\mathbf{L} \mathbf{1} = \mathbf{0} \text{。}
这一性质直接导致了节点电压方程的解不唯一。
1.4 二端驱动与等效电阻
现在考虑在节点 i 与 j 之间接入一个单位电流源（从 i 注入，从 j 流出）。此时节点注入电流向量为 \mathbf{i} = \mathbf{e}_i - \mathbf{e}_j （\mathbf{e}_k 为第 k 个标准基向量）。方程
\mathbf{L} \mathbf{v} = \mathbf{e}_i - \mathbf{e}_j
的解由于 \mathbf{L} \mathbf{1} = \mathbf{0} 而不唯一，但任意两解相差一个常数向量。我们固定一个节点的电压，例如令 v_j = 0 （“接地”），便可唯一确定所有节点电压。此时，端口 i, j 之间的等效电阻 R_{i, j} 恰为 i 的电压：
R_{i, j} = v_i \text{。}
从更一般的电路理论视角审视，Thévenin 定理 指出：任何线性双端网络都能等效为一个理想电压源与一个电阻的串联，而该电阻正是从端口看入的等效电阻。因此，对于本文所讨论的纯电阻网络，R_{i, j} 完全决定了端口的外特性，无论内部拓扑如何复杂。这为我们将网络抽象为图，并聚焦于生成树权的计算提供了坚实的物理依据。
2. Laplace 矩阵与矩阵树定理
2.1 矩阵树定理（加权形式）
定理（Kirchhoff 矩阵树定理） ：设 G 是连通的加权无向图，边权为电导 c_e > 0 ，\mathbf{L} 为对应的 Laplace 矩阵。对任意顶点 k ，记 \mathbf{L}^{(k)} 为删去 \mathbf{L} 的第 k 行与第 k 列后得到的 (n - 1) \times (n - 1) 矩阵。那么
\det \mathbf{L}^{(k)} = \sum_{T \text{ 是生成树}} \; \prod_{e \in T} c_e \text{。} \tag{1}
等式左边与选取的 k 无关（只要图是连通的）。若所有 c_e = 1 ，则 \det \mathbf{L}^{(k)} 就是生成树的总棵数。
2.2 证明概要
设 \mathbf{B}^{(k)} 是删去关联矩阵第 k 行所得的 (n - 1) \times m 矩阵。由 \mathbf{L} = \mathbf{B} \mathbf{C} \mathbf{B}^{\mathsf{T}} 立得 \mathbf{L}^{(k)} = \mathbf{B}^{(k)} \mathbf{C} (\mathbf{B}^{(k)})^{\mathsf{T}} 。应用 Cauchy–Binet 公式 ：
\det \bigl( \mathbf{A} \mathbf{D} \mathbf{A}^{\mathsf{T}} \bigr) = \sum_{\substack{S \subseteq \{1, \ldots, m\} \\ \lvert S \rvert = p}} \bigl( \det \mathbf{A}_S \bigr)^2 \prod_{e \in S} \mathbf{D}_{e, e} \text{，}
其中 \mathbf{A}_S 为 \mathbf{A} 中列指标属于 S 的子矩阵。取 \mathbf{A} = \mathbf{B}^{(k)} ，\mathbf{D} = \mathbf{C} ，p = n - 1 ，得到
\det \mathbf{L}^{(k)} = \sum_{\substack{S \subseteq E \\ \lvert S \rvert = n - 1}} \bigl( \det \mathbf{B}^{(k)}_S \bigr)^2 \prod_{e \in S} c_e \text{。}
图论中的一个经典事实是：\det \mathbf{B}^{(k)}_S \neq 0 当且仅当 S 构成一棵生成树，且此时行列式的值为 \pm 1 。平方后成为 1 ，从而求和恰为所有生成树的边权积之和。
2.3 小例子：三角形网络
三个节点的完全图，边电导分别为 c_{1, 2}, c_{2, 3}, c_{3, 1} 。它的 Laplace 矩阵为
\mathbf{L} =
\begin{bmatrix}
c_{1, 2} + c_{3, 1} & -c_{1, 2} & -c_{3, 1} \\
-c_{1, 2} & c_{1, 2} + c_{2, 3} & -c_{2, 3} \\
-c_{3, 1} & -c_{2, 3} & c_{3, 1} + c_{2, 3}
\end{bmatrix} \text{。}
删去第 3 行第 3 列得
\mathbf{L}^{(3)} =
\begin{bmatrix}
c_{1, 2} + c_{3, 1} & -c_{1, 2} \\
-c_{1, 2} & c_{1, 2} + c_{2, 3}
\end{bmatrix} \text{。}
其行列式为 c_{1, 2} c_{2, 3} + c_{2, 3} c_{3, 1} + c_{3, 1} c_{1, 2} ，正好是三棵生成树（依次缺少 \{1, 3\} 、\{1, 2\} 、\{2, 3\} 边）的权积之和，与定理吻合。
3. 等效电阻的行列式公式
3.1 用 Cramer 法则求解电压
回到驱动方程，已固定 v_j = 0 。记 \mathbf{L}^{(j)} 为删去第 j 行第 j 列的矩阵，相应的电流向量删去第 j 个分量后记为 \mathbf{e}_i' \in \mathbb{R}^{n - 1} （其第 i 个位置为 1 ，其余为 0 ），则方程化为 \mathbf{L}^{(j)} \mathbf{v}^{(j)} = \mathbf{e}_i' 。由 Cramer 法则 ，未知量 v_i 等于
v_i = \frac{\det \bigl( \mathbf{L}^{(j)} \text{ 的第 } i \text{ 列替换为 } \mathbf{e}_i' \bigr)}{\det \mathbf{L}^{(j)}} \text{。}
观察分子中的矩阵：将 \mathbf{L}^{(j)} 的第 i 列变成几乎全零、唯原 i 行处为 1 的列。按该列展开行列式，发现它等于同时删去第 i 行第 i 列与第 j 行第 j 列所得矩阵的正行列式 。记此矩阵为 \mathbf{L}^{(i, j)} ，于是得到 Kirchhoff 的等效电阻公式：
R_{i, j} = \frac{\det \mathbf{L}^{(i, j)}}{\det \mathbf{L}^{(i)}} \text{。} \tag{2}
（分母也可用 \det \mathbf{L}^{(j)} ，连通图中二者相等。）
3.2 组合意义：2-树（分离两点的生成森林）
矩阵树定理同样赋予 \det \mathbf{L}^{(i, j)} 组合解释。可以证明：
\det \mathbf{L}^{(i, j)} = \sum_{\text{分离 } i, j \text{ 的 2-树 } F} \; \prod_{e \in F} c_e \text{。}
这里所谓的 2-树 （two-tree）是电路分析中的历史术语，指将原图分割为两棵互不相交的树且覆盖全部 n 个顶点的生成森林，并且规定节点 i 与 j 必须位于不同的树中。注意 ：该概念与图论中的“树宽为 k 的极大图”所指的 k -树完全不同，切勿混淆。每棵这样的 2-树恰有 n - 2 条边，因此 \mathbf{L}^{(i, j)} 是 (n - 2) \times (n - 2) 方阵。
于是公式 (2) 可进一步写成
R_{i, j} = \frac{\sum_{\text{分离 } i, j \text{ 的 2-树 } F} \; \prod_{e \in F} c_e}{\sum_{T \text{ 是生成树}} \; \prod_{e \in T} c_e} \text{。} \tag{3}
直观解读 ：分母（所有生成树权之和）度量了整个网络连通“骨架”的总权重；分子（分离 i, j 的 2-树权之和）度量了在所有强制断开 i, j 的情形下，其余部分仍能连通的骨架权重总和。比值越大，意味着断开 i, j 后网络连通方式仍然很多，电流自然更难从 i 流向 j ，等效电阻也就越大。
4. 实例：Wheatstone 电桥（行列式法）
下面通过一个具体电路感受公式 (2) 的便捷。我们将电桥的电阻值设置得不完全对称，以打破平凡对称性。
电路描述 ：Wheatstone 电桥包含 5 个电阻，节点编号如下（亦可见寻常电路图）：
电阻值及电导：
求端口 (1, 4) 间的等效电阻 R_{1, 4} 。
步骤 1：写出 Laplace 矩阵 。
按定义，
\mathbf{L} =
\begin{bmatrix}
c_{1, 2} + c_{1, 3} & -c_{1, 2} & -c_{1, 3} & 0 \\
-c_{1, 2} & c_{1, 2} + c_{2, 3} + c_{2, 4} & -c_{2, 3} & -c_{2, 4} \\
-c_{1, 3} & -c_{2, 3} & c_{1, 3} + c_{2, 3} + c_{3, 4} & -c_{3, 4} \\
0 & -c_{2, 4} & -c_{3, 4} & c_{2, 4} + c_{3, 4}
\end{bmatrix} \text{。}
代入数值得（全部写成分数以便精确计算）
\mathbf{L} =
\begin{bmatrix}
\frac{3}{2} & -\frac{1}{2} & -1 & 0 \\[4pt]
-\frac{1}{2} & \frac{5}{2} & -1 & -1 \\[4pt]
-1 & -1 & \frac{5}{2} & -\frac{1}{2} \\[4pt]
0 & -1 & -\frac{1}{2} & \frac{3}{2}
\end{bmatrix} \text{。}
步骤 2：计算分母 \det \mathbf{L}^{(4)} 。
删去第 4 行第 4 列：
\mathbf{L}^{(4)} =
\begin{bmatrix}
\frac{3}{2} & -\frac{1}{2} & -1 \\[4pt]
-\frac{1}{2} & \frac{5}{2} & -1 \\[4pt]
-1 & -1 & \frac{5}{2}
\end{bmatrix} \text{。}
行列式展开：
\begin{aligned}
\det \mathbf{L}^{(4)} &= \frac{3}{2} \biggl( \frac{5}{2} \times \frac{5}{2} - (-1) \times (-1) \biggr) - \biggl( -\frac{1}{2} \biggr) \biggl( \biggl( -\frac{1}{2} \biggr) \times \frac{5}{2} - (-1) \times (-1) \biggr) + (-1) \biggl( \biggl( -\frac{1}{2} \biggr) \times (-1) - \frac{5}{2} \times (-1) \biggr) \\[4pt]
&= \frac{3}{2} \biggl( \frac{25}{4} - 1 \biggr) + \frac{1}{2} \biggl( -\frac{5}{4} - 1 \biggr) + (-1) \biggl( \frac{1}{2} + \frac{5}{2} \biggr) \\[4pt]
&= \frac{3}{2} \cdot \frac{21}{4} + \frac{1}{2} \cdot \biggl( -\frac{9}{4} \biggr) - 1 \cdot 3 \\[4pt]
&= \frac{63}{8} - \frac{9}{8} - 3 \\[4pt]
&= \frac{54}{8} - 3 = \frac{27}{4} - 3 = \frac{15}{4} \text{。}
\end{aligned}
所以 \det \mathbf{L}^{(4)} = \frac{15}{4} 。
步骤 3：计算分子 \det \mathbf{L}^{(1, 4)} 。
同时删去第 1 行第 1 列与第 4 行第 4 列，即保留第 2, 3 行及第 2, 3 列：
\mathbf{L}^{(1, 4)} =
\begin{bmatrix}
\frac{5}{2} & -1 \\[4pt]
-1 & \frac{5}{2}
\end{bmatrix} \text{。}
行列式为 \frac{5}{2} \times \frac{5}{2} - (-1) \times (-1) = \frac{25}{4} - 1 = \frac{21}{4} 。
步骤 4：代入公式 (2) 。
R_{1, 4} = \frac{\det \mathbf{L}^{(1, 4)}}{\det \mathbf{L}^{(1)}} = \frac{21 / 4}{15 / 4} = \frac{21}{15} = \frac{7}{5} = 1.4 \, \Omega \text{。}
（在下一节，我们将用图简化算法和 Y-Δ 变换再次得到相同结果。）
5. 快速简化算法与 Y-Δ 变换
第 4 节的行列式方法固然普适，但对于大规模网络，矩阵运算量可能很大。幸运的是，许多实际电路具有特殊的拓扑结构，我们可以通过图简化（graph reduction）高效计算生成树权之和，从而利用公式 (2) 快速得到等效电阻。
5.1 图简化与生成树计数
记 \tau(G) 为连通加权图 G 的生成树总权（即 \prod_{e \in T} c_e 在所有生成树上的和）。对于等效电阻公式 (2)，我们可以利用一个巧妙的关系：将节点 i 与 j 收缩 为一个新节点（等价于将两点等电势短接），记收缩后的图为 G / \{i, j\} ，则
\det \mathbf{L}^{(i, j)} = \tau(G / \{i, j\}) \text{。}
该结论的组合本质是：收缩 i 与 j 后，原来分离 i, j 的 2-树恰好一一对应于收缩图的生成树。因此，
R_{i, j} = \frac{\tau(G / \{i, j\})}{\tau(G)} \text{。} \tag{4}
于是问题转化为：如何快速计算一个加权无向图的 \tau(G) ？
对于树宽不超过 2 的图（即广义串并联图 ，generalized series-parallel graph），存在一套简洁的图简化规则，可在多项式时间内计算出 \tau(G) 。这类图等价于不包含 K_4 （4 阶完全图）细分的图，其每个双连通分量均可由一条边出发，反复施加串联和并联操作构造得到（这样的双连通分量称为串并联图）。
5.2 基本简化规则
在下述操作中，我们维护一个图 G 和一个乘子 \kappa （初始 \kappa = 1 ），使得当前图的 \tau(G_{\text{cur}}) 乘以 \kappa 等于原始图的 \tau(G) 。反复应用规则，直到图退化为单一节点（无边），此时约定 \tau(\text{单节点空图}) = 1 ，于是原始 \tau(G) = \kappa 。简化结果与消去节点的顺序无关。
规则 1：合并重边（并联）
若节点 u 与 v 之间有 k 条平行边，电导分别为 c_1, c_2, \ldots, c_k 。任何生成树中至多包含这些平行边中的一条，因此它们在生成树总权中的贡献等价于将它们替换为单条边，其电导为
c_{\text{new}} = c_1 + c_2 + \cdots + c_k \text{。}
操作：删除所有平行边，加入一条新边 (u, v) ，权为 c_{\text{new}} 。乘子 \kappa 不变。
规则 2：移去度 1 节点
若存在节点 v ，其度数为 1 ，仅有边 e = (u, v) 权为 c 。在任何生成树中，该边必须被选取（否则 v 孤立）。因此，所有生成树的权之和等于边 e 的权乘以删除 v 后剩余图的生成树权之和。操作：删除节点 v 及该边，并令 \kappa \gets \kappa \cdot c 。
规则 3：消去度 2 节点（串联简化）
若存在节点 v ，度数为 2 ，连接 u 与 w ，两条边的电导分别为 c_1 和 c_2 。这相当于一个串联结构。利用生成树的删除-收缩公式 ，可以严格证明消去 v 等效于如下操作（详细证明见下方折叠框）：删除 v 及其两条边，并在 u 与 w 之间添加一条新边，其电导为
c_{\text{new}} = \frac{c_1 c_2}{c_1 + c_2} \text{，}
同时将乘子 \kappa 乘以 (c_1 + c_2) ：
\kappa \gets \kappa \cdot (c_1 + c_2) \text{。}
若 u 与 w 之间原本已有边，则新边与旧边形成重边，可接着应用规则 1 合并。
::::info[证明：消去度 2 节点的串联公式（删除-收缩法）]
预备（删除-收缩公式） G 的非自环边 e （权 w_e ），生成树总权 \tau(G) 满足
\tau(G) = \tau(G \setminus e) + w_e \cdot \tau(G \mathbin{/} e) \text{，}
其中 G \setminus e 表示删除 e ，G \mathbin{/} e 表示收缩 e 。
定理 G 中顶点 v 恰有两个邻居 u 与 w ，边 v u 的权为 a ，边 v w 的权为 b 。从 G 中删去 v 及其两边，并在 u, w 间连一条权为 c = \frac{a b}{a + b} 的新边，所得之图记为 H 。则
\tau(G) = (a + b) \cdot \tau(H) \text{。}
证明 v u 用删除-收缩，再对得到的两项分别用边 v w 的删除-收缩。
在 G \setminus v u \setminus v w 中 v 孤立，故该项为 0 。
又 G \setminus v u \mathbin{/} v w 与 G \mathbin{/} v u \setminus v w 均与 H \setminus u w 相同，而 G \mathbin{/} v u \mathbin{/} v w 与 H \mathbin{/} u w 相同。由此计算：
\begin{aligned}
\tau(G) &= \tau(G \setminus v u) + a \cdot \tau(G \mathbin{/} v u) \\
&= [\tau(G \setminus v u \setminus v w) + b \cdot \tau(G \setminus v u \mathbin{/} v w)] + a \cdot [\tau(G \mathbin{/} v u \setminus v w) + b \cdot \tau(G \mathbin{/} v u \mathbin{/} v w)] \\
&= 0 + b \cdot \tau(H \setminus u w) + a \cdot \tau(H \setminus u w) + a b \cdot \tau(H \mathbin{/} u w) \\
&= (a + b) \cdot \tau(H \setminus u w) + a b \cdot \tau(H \mathbin{/} u w) \\
&= (a + b) \cdot \biggl[ \tau(H \setminus u w) + \frac{a b}{a + b} \cdot \tau(H \mathbin{/} u w) \biggr] \\
&= (a + b) \cdot [\tau(H \setminus u w) + c \cdot \tau(H \mathbin{/} u w)] \\
&= (a + b) \cdot \tau(H) \text{。}
\end{aligned}
末行即对 H 的边 u w 逆用删除-收缩公式。
::::
反复应用这三条规则，任何树宽不超过 2 的广义串并联图均可简化为单一节点。对于更一般的图，若遇到无法应用上述规则的节点，则可引入 Y-Δ 变换等进一步处理。
5.3 用简化法重算 Wheatstone 电桥的 R_{1, 4}
电导如前：c_{1, 2} = \frac{1}{2} ，c_{1, 3} = 1 ，c_{2, 4} = 1 ，c_{3, 4} = \frac{1}{2} ，c_{2, 3} = 1 。
（一）计算分母 \tau(G)
初始 \kappa = 1 。
节点 1 度数为 2 （边 (1, 2) 权 \frac{1}{2} ，边 (1, 3) 权 1 ）。应用规则 3：c_1 = \frac{1}{2} ，c_2 = 1 ，和 c_1 + c_2 = \frac{3}{2} 。
新边 (2, 3) 的权为
\frac{(1 / 2) \times 1}{3 / 2} = \frac{1 / 2}{3 / 2} = \frac{1}{3} \text{。}
乘子 \kappa = 1 \times \frac{3}{2} = \frac{3}{2} 。
删除节点 1 。此时图有节点 \{2, 3, 4\} ，边：(2, 3) 原权 1 ，新添权 \frac{1}{3} （重边）；(2, 4) 权 1 ；(3, 4) 权 \frac{1}{2} 。
合并 (2, 3) 重边，总权 1 + \frac{1}{3} = \frac{4}{3} 。乘子不变。
节点 4 度数为 2 （边 (4, 2) 权 1 ，边 (4, 3) 权 \frac{1}{2} ）。应用规则 3：c_1 = 1 ，c_2 = \frac{1}{2} ，和 \frac{3}{2} 。
新边 (2, 3) 权为
\frac{1 \times \frac{1}{2}}{3 / 2} = \frac{1 / 2}{3 / 2} = \frac{1}{3} \text{。}
乘子 \kappa = \frac{3}{2} \times \frac{3}{2} = \frac{9}{4} 。删除节点 4 ，图有节点 \{2, 3\} ，边：原 (2, 3) 权 \frac{4}{3} ，新添权 \frac{1}{3} （重边）。
合并重边，总权 \frac{4}{3} + \frac{1}{3} = \frac{5}{3} 。乘子不变。
此时仅剩边权 \frac{5}{3} 连接 2 与 3 。消去节点 3 （度 1 ），应用规则 2：边权 \frac{5}{3} ，\kappa = \frac{9}{4} \times \frac{5}{3} = \frac{45}{12} = \frac{15}{4} 。剩余单节点（无边），故 \tau(G) = \kappa = \frac{15}{4} 。与行列式结果一致。
（二）计算分子 \tau(G / \{1, 4\})
将节点 1 与 4 收缩为 S 。收缩图 H 的节点为 \{S, 2, 3\} 。边重连并合并：
原 (1, 2) 权 \frac{1}{2} 与 (4, 2) 权 1 合并为 (S, 2) 权 \frac{3}{2} 。
原 (1, 3) 权 1 与 (4, 3) 权 \frac{1}{2} 合并为 (S, 3) 权 \frac{3}{2} 。
原 (2, 3) 权 1 保留。
计算 \tau(H) ，初始 \kappa = 1 。
节点 3 度 2 （(S, 3) 权 \frac{3}{2} ，(2, 3) 权 1 ）。应用规则 3：c_1 = \frac{3}{2} ，c_2 = 1 ，和 \frac{5}{2} 。
新边 (S, 2) 权为
\frac{\frac{3}{2} \times 1}{5 / 2} = \frac{3 / 2}{5 / 2} = \frac{3}{5} \text{。}
乘子 \kappa = \frac{5}{2} 。删除节点 3 ，得节点 \{S, 2\} ，边：原 (S, 2) 权 \frac{3}{2} ，新添权 \frac{3}{5} （重边）。
合并重边，总权 \frac{3}{2} + \frac{3}{5} = \frac{21}{10} 。乘子不变。
节点 2 度 1 ，应用规则 2：删除 2 及边，\kappa = \frac{5}{2} \times \frac{21}{10} = \frac{21}{4} 。剩余单节点 S ，故 \tau(H) = \frac{21}{4} 。
代入公式 (4) 得
R_{1, 4} = \frac{21 / 4}{15 / 4} = \frac{21}{15} = \frac{7}{5} = 1.4 \, \Omega \text{。}
5.4 Y-Δ 变换
简化规则能完全处理广义串并联图。当图中出现度数不小于 3 且无法用串并联简化的节点时（例如完全二部图 K_{3, 3} ），图便不再是广义串并联图。历史上工程师们发明了 Y-Δ 变换 （星角变换），可将三端星形（Y）与角形（Δ）等价互化。
电阻形式的 Δ → Y 变换公式（已知角形三边电阻 R_{1, 2}, R_{2, 3}, R_{3, 1} ）：
\begin{aligned}
R_1 &= \frac{R_{1, 2} R_{3, 1}}{R_{1, 2} + R_{2, 3} + R_{3, 1}} \text{，} \\
R_2 &= \frac{R_{1, 2} R_{2, 3}}{R_{1, 2} + R_{2, 3} + R_{3, 1}} \text{，} \\
R_3 &= \frac{R_{2, 3} R_{3, 1}}{R_{1, 2} + R_{2, 3} + R_{3, 1}} \text{。}
\end{aligned}
Y → Δ 逆变换公式为 R_{1, 2} = R_1 + R_2 + \frac{R_1 R_2}{R_3} ，并可轮换下标得到 R_{2, 3} 与 R_{3, 1} 。注意变换过程中电导与电阻的关系，我们可根据需要选择使用电阻或电导形式。
两种 Δ → Y 与 Y → Δ 的变换统称为 Y-Δ 变换。
5.4.1 用 Y-Δ 变换计算 Wheatstone 电桥的 R_{1, 4}
仍取上例：R_{1, 2} = 2 \, \Omega ，R_{1, 3} = 1 \, \Omega ，R_{2, 4} = 1 \, \Omega ，R_{3, 4} = 2 \, \Omega ，R_{2, 3} = 1 \, \Omega 。注意到节点 1 、2 、3 连同它们之间的三条边构成一个角形（Δ），其总电阻和为 R_{\text{sum}} = 2 + 1 + 1 = 4 \, \Omega 。对该角形实施 Δ→Y 变换，得到一个星形，中心记作 O ，各臂电阻为：
原角形被移除，留下中心节点 O 与 1, 2, 3 相连，而节点 4 仍通过原有电阻与 2, 3 相连。新的网络结构为：从端子 1 到 O 的电阻 0.5 \, \Omega ，从 O 到 2 的电阻 0.5 \, \Omega ，2 到 4 的电阻 1 \, \Omega （串联路径）；同时从 O 到 3 的电阻 0.25 \, \Omega ，3 到 4 的电阻 2 \, \Omega （另一条串联路径）。这两条路径在 O 与 4 之间并联。因此，O 到 4 的等效电阻为：
上支路（经 2 ）：R_{\text{upper}} = 0.5 + 1 = 1.5 \, \Omega ；
下支路（经 3 ）：R_{\text{lower}} = 0.25 + 2 = 2.25 \, \Omega ；
并联等效：R_{O4} = \frac{1.5 \times 2.25}{1.5 + 2.25} = \frac{3.375}{3.75} = 0.9 \, \Omega 。
最后，端口 1 与 4 之间的总电阻为 R_{1O} 与 R_{O4} 的串联：
R_{1, 4} = 0.5 + 0.9 = 1.4 \, \Omega \text{，}
再次与行列式法和简化法的结果完美吻合。Y-Δ 变换将桥式电路的非串并联结构化解，展示了其灵活性。
5.5 算法适用范围与局限
并非所有图都能通过有限次 Y-Δ 变换化为广义串并联图。著名的 Petersen 图便是一个不可约的例子。能够通过 Y-Δ 变换以及广义串并联图的简化操作最终简化为单个点的图称为 YΔY 可约图 ，它们构成比广义串并联图更宽泛的一类图，甚至于全体平面图均是 YΔY 可约的，但仍有其局限性。因此，普适的等效电阻计算依然离不开 Laplace 矩阵与行列式框架。
6. 拓展：电阻距离与随机游走
等效电阻 R_{i, j} 在现代图论中被重新诠释为电阻距离 （resistance distance）。它满足距离的全部公理，并且与随机游走有着简明的联系：对于无权的连通图（所有 c_e = 1 ），随机游走从 i 到 j 的期望往返时间（commute time）为
\operatorname{CommuteTime}(i, j) = 2 m R_{i, j} \text{，}
其中 m 是图的边数。对于加权图（边权为电导），若随机游走的转移概率按边权分配，则相应公式为
\operatorname{CommuteTime}(i, j) = 2 \Biggl( \sum_{e \in E} c_e \Biggr) R_{i, j} \text{。}
此外，Laplace 矩阵的谱（特征值）也与电阻距离紧密相关——例如第二特征值 \lambda_2 （代数连通度）能给出电阻距离的上下界，刻画了图的连通程度对电流传播的制约。这些联系使得 Kirchhoff 的经典理论持续在复杂网络分析、机器学习等领域熠熠生辉。
关于这部分内容在算法竞赛中的介绍，可参考 APIO 2025 中罗思远的《电阻网络与随机游走》一课的材料。
7. 结语
Kirchhoff 矩阵树定理是图论与线性代数结合的典范，而将它重新投入电路计算的熔炉，又能锻造出任意电阻网络等效电阻的简洁行列式公式。从关联矩阵到生成树，从分离两点的生成森林到行列式比值，我们见证了数学不同分支之间的美妙共鸣。广义串并联简化与 Y-Δ 变换则提供了实践中重要的快速计算手段，而行列式方法始终扮演着普适性框架的角色。希望这篇文章能帮助你建立对矩阵树定理的直观理解，并感受到它那“一理通，百理明”的强大威力。
免责声明：上面这一段漂亮话全部是 DeepSeek 写的。