计算纯电阻网络的等效电阻

计算纯电阻网络的等效电阻，与计算烷烃的同分异构体数量，是许多学习 OI 的高中生想要解决的问题。不过相比于计算烷烃的同分异构体数量而言，这个问题简单很多。本文将介绍一种简单的等效电阻计算方法，并给出一个计算所有接入电路方案的等效电阻的算法。

基本概念

上图是电阻网络的一个示意图。其中矩形表示纯电阻，上面可能会标注它的阻值。粗线表示导线，导线的交点通常会是接线柱之类的东西，称之为节点，可以连入外部电路。我们的目标是，给出这个网络的结构、每个电阻的阻值以及接入外电路的两个节点（一个是电流流入的位置，另一个是电流流出的位置，如上图中的左边和右边两个不闭合的导线），计算出它的等效电阻，即电流经过电阻网络时的电压 $U$ 与流入电流 $I$ 之比。例如，上图表示的电阻网络的等效电阻为 $159/71\;\Omega \approx 2.239\;\Omega$。

为了方便表示，这里将电阻网络转为图论的模型。图中一共有 $n$ 个节点和 $m$ 个电阻，每个节点对应图中的点，每个电阻对应图中的一条边，用边权表示电阻的阻值。例如，上面展示的电阻网络可以表示为下面的形式：

接入电路后，每个电阻上都会通有电流，记为 $I$。电流有方向之分，如果某条边 $(u,\;v)$ 上的的电流是从 $u$ 流向 $v$ 的，那么 $I_{uv} = -I_{vu} \geqslant 0$。设这条边的电阻为 $R_{uv} = R_{vu}$，那么它的电压为 $U_{uv} = -U_{vu} = I_{uv}R_{uv}$。

为了方便，我们称外部电流流入网络的节点为源点 $s$，从网络流出到外部电路的节点为汇点 $t$，$(s,\;t)$ 称作一个点对。显然不同的源点和汇点计算出来的等效电阻会是不同的。

计算一个点对

首先我们需要知道比较直观的基尔霍夫定律：

基尔霍夫电流定律：所有进入某节点的电流的总和等于所有离开该节点的电流的总和。

基尔霍夫电压定律：沿着闭合回路所有元件两端的电压的代数和等于零。

根据这两点，如何求出等效电阻呢？首先可以假定流入的电流为 $1\;\mathrm{A}$，然后就只需求出源点到汇点的电压即可。根据电压定律，我们可以知道从源点到汇点的任意一条路径的电压是定值。原因非常简单，对于两条不同的路径：

如果存在不重合的部分，我们对这个部分进行调整，在电压不变的情况下，将一条路径变为另外一条路径。如上图，设左边的分岔点为 $A$，右边的分岔点为 $B$，由于回路电压为 $0$，所以下面那一条从 $A$ 到 $B$ 的路径的电压 $U_1$ 与从 $B$ 到 $A$ 的电压 $U_2$ 的代数和为 $0$，即 $U_1 + U_2 = 0$，而靠上面的从 $A$ 到 $B$ 的电压 $U_3 = -U_2$，因此 $U_1 = U_3$，从而发现上述规律。由于假定流入的电流是 $1\;\mathrm{A}$，所以等效电阻等于电压的绝对值。

为了求出电压，我们可以考虑求出每个电阻上的电流的情况。根据电流定律，对于每个节点，我们可以列出 $n$ 个方程。不过很不幸，这 $n$ 个方程中任意一个都可以被剩下 $n - 1$ 个方程表示出来，意思是我们只有 $n - 1$ 个方程是真正有用的。边数一共有 $m$ 条，也就是 $m$ 个未知数，还需要找出 $m - n + 1$ 个线性独立的方程才可以解出具体情况。碰巧的是，如果网络是连通的，那么对于它的任意一棵生成树，刚好有 $m - n + 1$ 条非树边，每条非树边均对应了一个环，可以依此和电压定律列出剩下的方程。

得到了 $m$ 个方程，就可以直接使用高斯消元在 $\Theta(m^3)$ 的时间复杂度内求出电流的分配情况了。得到每个电阻上经过的电流后，从源点到汇点任意找一条路径计算电压，就可以知道等效电阻。一般我们会选取 DFS 生成树来列出电压的方程，主要的原因就是 DFS 生成树上的非树边都是返祖边，方便遍历对应的环上的所有的边。

我使用 Python 实现了上面所说的过程。不过偷了懒，是用 SymPy 解的方程......所以算的不是很快。具体的代码可以查看这里。

计算所有点对

想到可以计算所有点对等效电阻的初衷是由于计算不同点对时的列出方程组其实没有多大差别，只有源点和汇点列出的电流方程存在着一个常数。根据这一点，我们不妨多写几个变量 $x_1,\;x_2,\;...,\;x_{n - 1}$，表示每个节点从外部电路得到的电流。之所以只到 $x_{n - 1}$，是因为电流方程只列出了 $n - 1$ 个。如果 $x_i = 0$ 表示节点 $i$ 没有直接与外部电路相连，而 $x_i = 1$ 和 $x_i = -1$ 分别表示从外部电路流入和流出到外部电路。在不预先指定源点和汇点的情况下把它们当做已知量写入方程。虽然现在有 $m + n - 1$ 个未知数却只有 $m$ 个方程，但是这个时候执行高斯消元可以得到每个电流与 $x_1,\;...,\;x_{n-1}$ 的关系（如 $I_1 = 2x_1 + 0.3x_3$）。如果再给出 $x_1,\;...,\;x_{n - 1}$ 的值，就可以直接算出每个电流的具体值。

现在来指定源点 $s$ 和汇点 $t$。相当于之前新设的变量中，令 $x_s = 1$ 和 $x_t = -1$，其它的均为 $0$。因此只用 $\Theta(n)$ 的时间就可以计算出所有电流值，也就可以算出电阻。由于点对总数只有 $\Theta(n^2)$ 对，因此高斯消元后只需要 $\Theta(n^3)$ 的时间就可以计算所有的等效电阻。在连通图中，存在 $m \geqslant n - 1$，因此总的复杂度依然为 $\Theta(m^3)$。

我的 C++ 实现可以在这里查看。