有效电阻初探

有效电阻是电磁学电路问题中的基本概念，在图论中亦有这重要地位。

引入

对于一个电阻网络中的两个点 $u,v$，由欧姆定律，这两个点之间的有效电阻定义为：电流 $I$ 从 $u$ 注入，并全部从 $v$ 流出时，两点的电势差与 $I$ 的比值。即：

$R(u,v)=\dfrac{U(u,v)}{I}$

其中 $R(u,v)$ 表示 $u,v$ 间的有效电阻，$U(u,v)$ 表示 $u,v$ 间的电势差。

本文将用矩阵与图论的语言推导一般电阻网络中两点间有效电阻的表达式。

记号与规定

本文中的图若无特殊说明都是有限的无向简单连通图。并且对于一个图 $G=(V,E)$，顶点编号都默认从 $1$ 到 $|V|$，而边的编号都默认从 $1$ 到 $|E|$。

本文中的向量均用粗体表示，且默认都是列向量，而对应下标的元素的值用非粗体字母加上括号下标的方式表示。如：对于向量 $\bm{v}\in \mathbb R^n$，其表示为：$\bm{v}=(v(1),v(2),\ldots,v(n))^\top$。用 $|\bm{v}|=\sqrt{\bm{v}^\top\cdot \bm{v}}$ 表示向量 $\bm{v}$ 的模长。

本文中用 $\delta_i$ 表示除了第 $i$ 位为 $1$ 其余位均为 $0$ 的行向量，即：$\delta_i=(0,\ldots,\mathop{1}\limits^{i},\ldots,0)$，保证向量的长度通过上下文是自明的。

对于一个矩阵 $A\in \mathbb R^{m\times n}$，本文做如下记号规定：

• 用 $A(i,j)\,(i=1,2,\ldots,m,j=1,2,\ldots,n)$ 表示矩阵第 $i$ 行第 $j$ 列的元素的值。
• 用 $A_i\,(i=1,2,\ldots,m)$ 表示矩阵 $A$ 的第 $i$ 的所有元素组成的行向量，即 $A_i=(A(i,1),A(i,2),\ldots,A(i,n))$。
• 用 $\text{span}(A)$ 表示矩阵 $A$ 所有列向量张成的空间。

图的拉普拉斯矩阵

给定一张无向图 $G=(V,E)$，其度数矩阵为：

$D=\text{diag}(\text{deg}(1),\text{deg}(2),\ldots,\text{deg}(|V|))$

其中 $\text{deg}(i)$ 表示编号为 $i$ 的节点的度数。

邻接矩阵为：

$A(i,j)=[(i,j)\in E]\,(i,j=1,2,\ldots,|V|)$

则定义图 $G$ 的拉普拉斯矩阵为：$L=D-A$。

拉普拉斯矩阵有如下几个性质。

定理 $1$：$0$ 是 $L$ 的特征值，且 $\bm{1}$ 是 $0$ 对应的一个特征向量，其中 $\bm{1}$ 为全 $1$ 向量。

证明：

$\forall u\in V, (L\cdot \bm{1})(u)=\text{deg}(u)-\sum_{v\in V}[(u,v)\in E]=0$

$\Longrightarrow L\cdot \bm{1}=\bm{0}$

其中 $\bm{0}$ 是全 $0$ 向量。故得证。$\Box$

定理 $2$：
$L$ 是实对称矩阵，且对于任意实向量 $\bm{x}\in \mathbb R^{|V|}$，有：

$\bm{x}^\top L\bm{x}=\dfrac 12 \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)(x(i)-x(j))^2$

再进而可以得出 $L$ 是半正定的。

证明：$L$ 显然是对称的。而对任意 $\bm{x}\in \mathbb R^{|V|}$，有：

$\begin{aligned} \bm{x}^\top L\bm{x} & =\bm{x}^\top D\bm{x}-\bm{x}^\top A\bm{x} \\ & =\sum_{i=1}^{|V|} \text{deg}(i)x^2(i)-\sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)x(i)x(j) \\ & =\dfrac 12\left(\sum_{i=1}^{|V|} \text{deg}(i)x^2(i)-2\sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)x(i)x(j)+\sum_{j=1}^{|V|} \text{deg}(j)x^2(j)\right) \\ & =\dfrac 12\left(\sum_{i=1}^{|V|} \sum_{j=1}^{|V|} A(i,j)x^2(i)-\sum_{i=1}^{|V|}\sum_{j=1}^{|V|}2A(i,j)x(i)x(j)+\sum_{j=1}^{|V|} \sum_{i=1}^{|V|} A(j,i)x^2(j)\right) \\ & =\dfrac 12 \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)(x(i)-x(j))^2 \end{aligned}$

有这个表达式很容易得到 $L$ 是半正定的。故得证。$\Box$

定理 $3$：如果无向图 $G$ 是连通图，则特征值 $0$ 的代数重数与几何重数都是 $1$，进而 $\text{rank}(L)=|V|-1$。更进一步，如果 $G$ 有 $k$ 个连通分量，则特征值 $0$ 的代数重数与几何重数都是 $k$，并且 $\text{rank}(L)=|V|-k$。

证明：因为 $L$ 是实对称矩阵，故特征值的代数重数与几何重数相同，下面统称为重数。

假设 $\bm{x}$ 是特征值 $0$ 对应的一个特征向量，则考虑如下二次型：

$0=\bm{x}^\top\cdot\bm{0}=\bm{x}^\top L\bm{x}=\dfrac 12 \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)(x(i)-x(j))^2$

则上式成立当且仅当所有的 $x(i)\,(i=1,2,\ldots,|V|)$ 是相同的，所以 $\bm{x}=|\bm{x}|\bm{1}$。

所以特征值 $0$ 对应的重数就是 $1$，进而 $\text{rank}(L)=|V|-1$。

对于有 $k$ 个连通分量的情况将矩阵的形式改写为分块对角矩阵容易证明。本文讨论的都是连通图，故略去这一部分的证明。$\Box$

有效电阻

给定一个图 $G=(V,E)$ 表示一个有限电阻网络图。定义图 $G$ 的关联矩阵 $B\in \mathbb R^{|E|\times |V|}$ 为：

$B(e,u)= \begin{cases} 1 & u\text{是}e\text{的起点} \\ -1 & u\text{是}e\text{的终点} \\ 0 & \text{otherwise} \end{cases}$

值得注意的是虽然我们是在无向图上讨论，但是我们可以给每一条边都定向。而下面这个定理告诉我们定向的方式对 $B^\top B$ 是不影响的。

定理 $4$：给定无向连通图 $G=(V,E)$，则不管给 $G$ 中的边如何定向，$B$ 如何选择，都有：$L=B^\top B$，其中 $L$ 为 $G$ 的拉普拉斯矩阵。

证明：对二元组 $(u,v)\in V\times V$ 进行分类讨论：

• 若 $u\ne v$。则对于任何 $e\in E$，$|B(e,u)|=|B(e,v)|=1\ne 0$ 当且仅当 $e=(u,v)$。

  又因为 $G$ 是简单图无重边，所以如果 $e$ 存在，则其唯一，并有 $A(u,v)=1$。如果 $e$ 不存在就有 $A(u,v)=0$。又因为有 $D(u,v)=0$，故：

$(B^\top B)(u,v)=-[(u,v)\in E]=D(u,v)-A(u,v)$

• 若 $u=v$。因为 $G$ 是简单图无自环，故 $A(u,u)=0$.又因为有 $D(u,u)=\text{deg}(u)$，故：

$(B^\top B)(u,v)=\sum_{e=(u,*)\in E}B^\top(u,e)B(e,u)=\sum_{e=(u,*)\in E}1=\text{deg}(u)=D(u,u)-A(u,u)$

综上可得：$B^\top B=D-A=L$，得证。$\Box$

如果给定了每个点的电压分布 $\bm{\phi}\in \mathbb R^{|V|}$，则由欧姆定律，一条边 $e=(u,v)\in E$ 上的方向电流 $I(e)$ 为：

$I(e)=\dfrac{\phi(u)-\phi(v)}{r(e)}$

其中 $r(e)$ 为 $e$ 这条边的电阻值。为了方便起见我们先在单位电阻网络（$\forall e\in E,r(e)=1$）上分析。那么 $I(e)$ 在数值上就等于 $\phi(u)-\phi(v)$。所以：

$I(e)=\phi(u)-\phi(v)=(\delta_u-\delta_v)\cdot \bm{\phi}=B_e\cdot \bm{\phi}$

我们把每个 $I(e)$ 的结果拼在一起组成一个向量 $\bm{I}\in \mathbb R^{|E|}$，则有：

$\bm{I}=B\bm{\phi}$

再定义一个节点 $u$ 的净流出电流 $f(u)$ 为：

$f(u)=\sum_{e=(u,v)\in E}I(e)-\sum_{e=(v,u)\in E}I(e)=(B^\top)_u\cdot \bm{I}$

同样的我们把每个 $f(u)$ 的结果拼在一起组成一个向量 $\bm{f}\in \mathbb R^{|V|}$，则有：

$\bm{f}=B^\top\bm{I}=B^\top B\bm{\phi}$

考虑当电流 $I$ 从 $u$ 点注入然后全部从 $v$ 点出来的时候。方便起见，我们令 $I$ 是单位电流。则除了 $u,v$ 点之外其它点的净流出电流均为 $0$，而 $u$ 为 $1$，$v$ 为 $-1$，即：

$\bm{f}=(\delta_u-\delta_v)^\top$

再回顾一下，我们有图的拉普拉斯矩阵 $L=B^\top B$，那么就有：

$(\delta_u-\delta_v)^\top=L\bm{\phi}$

由有效电阻的定义可得：

$R(u,v)=\dfrac{\phi(u)-\phi(v)}{I}$

因为 $I$ 为单位电流，所以 $R(u,v)$ 在数值上就等于 $\phi(u)-\phi(v)$。

那么现在问题就变为了求向量 $\bm{\phi}$，使得其满足 $(\delta_u-\delta_v)^\top=L\bm{\phi}$。

如果 $L$ 可逆，则可以直接得出唯一的 $\bm{\phi}$。但实际上根据电势定义知道电势的绝对大小是没有意义的，只有相对大小有意义。所以如果 $\bm{\phi}_0$ 为一满足条件的解，则对于任意实数 $t$，$\bm{\phi}_0+t\cdot \bm{1}$ 都是满足条件的解。

于是我们现在要想办法解出一个特解，这就是下面这个定理在干的事情。

定理 $5$：由定理 $2$ 可知 $L$ 可以相似对角化，设 $L$ 的对角化结果为：

$L=P^{-1}\text{diag}(\Lambda,0)P=P^\top\text{diag}(\Lambda,0)P=\sum_{i=1}^{|V|-1}\lambda_i \bm{v}_i\bm{v}^\top_i$

其中 $P$ 是正交阵，而由定理 $3$ 可知 $\Lambda$ 是一可逆对角阵。

考虑 $L$ 的广义逆为：

$L^+=P^\top\text{diag}(\Lambda^{-1},0)P=\sum_{i=1}^{|V|-1}\lambda_i^{-1}\bm{v}_i\bm{v}^\top_i$

那么非齐次线性方程组 $(\delta_u-\delta_v)^\top=L\bm{\phi}$ 有解，并且一个特解为 $\bm{\phi}_0=L^+ (\delta_u-\delta_v)^\top$，进而通解为 $\bm{\phi}=\bm{\phi}_0+t\cdot \bm{1}\,(t\in \mathbb R)$。

证明：首先先证明这个方程有解：

$\text{span}(L)=\text{span}\left(\sum_{i=1}^{|V|-1}\lambda_i\bm{v}_i\bm{v}^\top_i+0\cdot \bm{1}\cdot \bm{1}^\top \right)=\text{span}(\bm{v}_1,\bm{v}_2,\ldots,\bm{v}_{|V|-1})=(\text{span}(\bm{1}))^{\bot}$

又因为 $(\delta_u-\delta_v)^\top\cdot \bm{1}=0$，所以 $(\delta_u-\delta_v)^\top\in (\text{span}(\bm{1}))^{\bot}$，故此非齐次线性方程组有解。

设 $(\delta_u-\delta_v)^\top$ 在规范正交基 $\bm{v}_1,\ldots,\bm{v}_{|V|-1},\bm{1}/\sqrt{|V|}$ 下的坐标为 $(\alpha_1,\ldots,\alpha_{|V|-1},0)$。

那么：

$\bm{\phi}_0=L^+ (\delta_u-\delta_v)^\top=\left(\sum_{i=1}^{|V|-1}\lambda_i^{-1}\bm{v}_i\bm{v}^\top_i\right)\left(\sum_{i=1}^{|V|-1}\alpha_i\bm{v}_i\right)=\sum_{i=1}^{|V|-1}\dfrac{\alpha_i}{\lambda_i}\bm{v}_i$

所以：

$L\bm{\phi}_0=\left(\sum_{i=1}^{|V|-1}\lambda_i\bm{v}_i\bm{v}^\top_i\right)\left(\sum_{i=1}^{|V|-1}\dfrac{\alpha_i}{\lambda_i}\bm{v}_i\right)=\sum_{i=1}^{|V|-1}\alpha_i\bm{v}_i=(\delta_u-\delta_v)^\top$

故 $\bm{\phi}_0$ 是该方程一特解，得证。值得注意的是上述推导中用到了正交基的性质。$\Box$

综上我们可以写出有效电阻的矩阵表达式：

$R(u,v)=(\delta_u-\delta_v)\bm{\phi}=(\delta_u-\delta_v)L^{+}(\delta_u-\delta_v)^\top$

若 $(u,v)$ 是图 $G$ 的一条边 $e$，则因为有 $B_e=\delta_u-\delta_v$，所以上式可以改写为：

$R(e)=B_eL^{+}B_e^\top$

如果不是单位电阻网络，我们发现其实完全是一样的。只需要把 $B_e$ 改成 $\dfrac 1{r(e)}(\delta_u-\delta_v)\,(r(e)\in \mathbb R^+)$ 就可以了，后面的推导完全适用也完全一样。

有效电阻的性质

下面对有效电阻性质的讨论都是在简单无向连通的单位电阻网络图上讨论的。

定理 $6$：所有边有效电阻之和与边数无关：

$\sum_{(u,v)\in E}R(u,v)=|V|-1=\text{rank}(L)$

证明：

$\begin{aligned} \sum_{(u,v)\in E}R(u,v) & =\sum_{(u,v)\in E}(\delta_u-\delta_v)L^{+}(\delta_u-\delta_v)^\top \\ & =\text{tr}\left( \begin{pmatrix} B_{e_1} \\ \vdots \\ B_{e_{|E|}} \end{pmatrix} L^{+} \begin{pmatrix} B_{e_1}^\top & \ldots & B^\top_{e_{|E|}} \end{pmatrix} \right) \\ & =\text{tr}(BL^{+}B^\top)=\text{tr}(L^{+}B^\top B)=\text{tr}(L^{+}L) \\ & =\text{tr}(P^{-1}\text{diag}(\Lambda^{-1},0)PP^{-1}\text{diag}(\Lambda,0)P) \\ & =\text{tr}(P^{-1}P\text{diag}(I,0))=|V|-1=\text{rank}(L) \end{aligned}$

得证。值得注意的是上述推导中反复用到了迹中乘法可交换的性质。$\Box$

多加一条边可以理解为“并联”了，而有效电阻的和不变，所以每个都会变小，这也符合电学知识。

定理 $7$：对于图 $G$ 的一条边 $e\in E$，其有效电阻衡量了这一条边对整个电阻网络的能量贡献：

$R(e)=\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{|B\bm{x}|^2}$

证明：我们发现：$\{B\bm{x}\mid \bm{x}\in \mathbb R^{|V|} \}=\text{span}(B)$。所以其实有：

$\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{|B\bm{x}|^2}=\max\limits_{\bm{x}\in \text{span}(B)}\dfrac{x^2(e)}{|\bm{x}|^2}=\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B'_e\bm{x})^2}{|B'\bm{x}|^2}$

其中 $B'$ 满足 $\text{span}(B)=\text{span}(B')$。令：

$B'=B\sqrt{(B^\top B)^+}$

可以开平方是因为 $L=B^\top B$ 是半正定矩阵有唯一的正平方根。所以：

$\begin{aligned} B'^\top B' & =\sqrt{L^+}B^\top B\sqrt{L^+}=\sqrt{L^+}L\sqrt{L^+} \\ & =\left(\sum_{i=1}^{|V|-1}\lambda_i^{-1/2}\bm{v}_i\bm{v}_i^\top\right)\left(\sum_{i=1}^{|V|-1}\lambda_i\bm{v}_i\bm{v}_i^\top\right)\left(\sum_{i=1}^{|V|-1}\lambda_i^{-1/2}\bm{v}_i\bm{v}_i^\top\right) \\ & =\text{diag}(I,0) \end{aligned}$

因为 $B\cdot\bm{1}=\bm{0}$，所以 $\text{rank}(B)\le |V|-1$。再结合上式就可以发现 $B'$ 的前 $|V|-1$ 个列向量是两两正交的，而且有 $\text{span}(B)=\text{span}(B')$，即 $B'$ 给出了 $\text{span}(B)$ 的规范正交基。

这样我们就可以推导了：

$\begin{aligned} \max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{|B\bm{x}|^2} & =\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B'_e\bm{x})^2}{|B'\bm{x}|^2} \\ & =\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{\left(B_e\sqrt{(B^\top B)^+}\bm{x}\right)^2}{|\bm{x}|^2} \\ & =B_e(B^\top B)^+B_e=R(e) \end{aligned}$

得证。其中从第一行到第二行把分母上的 $B'$ 扔掉是因为 $B'$ 给出了规范正交基，有 $|B'\bm{x}|=|\bm{x}|$。从第二行到第三行是因为向量内积的性质，必然是当 $\bm{x}$ 与另一个向量 $\left(B_e\sqrt{(B^\top B)^+}\right)^\top$ 同向时取到最大值。$\Box$

这条性质可以这么理解：

$|B\bm{x}|^2=\bm{x}^\top B^\top B\bm{x}=\bm{x}^\top L\bm{x}=\dfrac 12 \sum_{i=1}^{|V|}\sum_{j=1}^{|V|}A(i,j)(x(i)-x(j))^2=\sum_{(u,v)\in E}(x(u)-x(v))^2$

如果把 $\bm{x}$ 理解为加上的电压分布，那么有 $(x(u)-x(v))^2=U^2(u,v)=U^2(u,v)/r((u,v))$，所以 $|B\bm{x}|$ 就是加上电压 $\bm{x}$ 后整个电阻网络的总能量，同样的 $(B_e\bm{x})^2=(x(u)-x(v))^2$ 是这条边的能量。

所以 $R(e)$ 就是任意加电压时一条边的能量比去总能量的最大值。

定理 $8$：对于图 $G$ 的一条边 $e\in E$，其有效电阻衡量了这一条边的重要程度：

$R(e)=\min\limits_{\bm{y}\in \mathbb R^{|E|}\text{ and }B^\top\bm{y}=B^\top_e}|\bm{y}|^2$

证明：一方面有：

$\begin{aligned} \min\limits_{\bm{y}\in \mathbb R^{|E|}\text{ and }B^\top\bm{y}=B^\top_e}|\bm{y}|^2 & \le |B(B^\top B)^+B_e^\top|^2 \\ & =B_e(B^\top B)^+B^\top B(B^\top B)^+B_e^\top=B_eL^+LL^+B_e^\top \\ & =B_e\left(\sum_{i=1}^{|V|-1}\lambda_i^{-1}\bm{v}_i\bm{v}_i^\top\right)\left(\sum_{i=1}^{|V|-1}\lambda_i\bm{v}_i\bm{v}_i^\top\right)\left(\sum_{i=1}^{|V|-1}\lambda_i^{-1}\bm{v}_i\bm{v}_i^\top\right)B_e^\top \\ & =B_eL^+B_e^\top=R(e) \end{aligned}$

上述推导的不等号成立是因为由定理 $5$ 的证明过程可知 $\bm{y}=B(B^\top B)^+ B_e^\top$ 是方程 $B^\top\bm{y}=B^\top_e$ 的一个解。

记上面 $\min$ 的最小值点为 $\bm{y}_0$，则另一方面又有：

$\begin{aligned} R(e) & =\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{|B\bm{x}|^2}=|\bm{y}_0|^2\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{|B\bm{x}|^2|\bm{y}_0|^2} \\ & \le |\bm{y}_0|^2\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{(\bm{y}_0^\top B\bm{x})^2} \\ & =|\bm{y}_0|^2\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{((B^\top\bm{y}_0)^\top\bm{x})^2}=|\bm{y}_0|^2\max\limits_{\bm{x}\in \mathbb R^{|V|}}\dfrac{(B_e\bm{x})^2}{(B_e\bm{x})^2} \\ & =|\bm{y}_0|^2=\min\limits_{\bm{y}\in \mathbb R^{|E|}\text{ and }B^\top\bm{y}=B^\top_e}|\bm{y}|^2 \end{aligned}$

故得证。值得注意的时上述推导用到了柯西不等式，而倒数第二行的推导用到了条件 $B^\top\bm{y}_0=B_e^\top$。$\Box$

有效电阻的拓展——杠杆值

对于一个有 $m$ 个 $n$ 维数据的实数数据集，我们用一个 $m\times n$ 的实数矩阵 $A\in \mathbb R^{m\times n}$ 表示这个数据集。

我们定义第 $i$ 个数据的杠杆值为：

$\tau_i(A)=A_i(A^\top A)^+ A_i^\top$

这个定义与有效电阻的矩阵表达如出一辙，推导后即可发现，杠杆值也继承了有效电阻的所有性质。杠杆值的大小代表了这个数据点在整个数据集中的重要程度，这怎么理解呢？我们看定理 $8$，有：

$\tau_i(A)=\min\limits_{\bm{y}\in \mathbb R^m\text{ and }A^\top\bm{y}=A^\top_i}|\bm{y}|^2$

$\bm{y}$ 要满足的条件是 $A^\top\bm{y}=A^\top_i$，即有：$A_i=y(1)A_1+y(2)A_2+\cdots+y(m)A_m$，$\bm{y}$ 给出了这样的线性组合系数。而如果 $|\bm{y}|$ 的最小值越小那么这个数据点就越容易被其他数据点线性表示，那么这个数据点就没有什么用处了。

值得注意的是 $\tau_i(A)$ 的取值有范围：$\tau_i(A)\in [0,1]$，这是因为 $A_i=1\cdot A_i$，所以 $\min|\bm{y}|\le 1$。如果一个数据点的杠杆值为 $1$，那这个数据点和其他的数据点都线性无关，这个数据点非常特殊，非常重要。

参考文献

[1] 科普文章丨经典有效电阻与现代矩阵算法. 蔡东润, 陈雪, 2023. site:
https://mp.weixin.qq.com/s/d3TQEM3IyUHsGcyMMyCL2A