09-网络上的随机游走二

回顾

电势 是

上的调和函数。与电势 相联系的电流 定义为

有效电阻定义为

与逃逸概率的关系

今天的目标

• 用于简化网络的三种操作；
• 有效电阻与流的能量；
• 纳什—威廉姆斯不等式。

简化网络的三种操作

下面介绍三种简化网络、同时不改变所关注量的操作。在下列操作之下，所有相关电势和电流均保持不变。

1. 并联定律： 并联电导相加。
2. 串联定律： 串联电阻相加。
3. 粘合： 将电势相同的顶点视为同一个顶点。

例：有偏最近邻随机游走. 固定 ，考虑顶点集合

构成的路径，并对 赋予边电导

网络的关系可以写成

考虑该网络上的随机游走，则从 出发，先到达 而不是先到达 的概率为

流的能量

定义. 流 的能量定义为

其中求和遍历所有无向边。

定理（有效电阻与流的能量）. 对任意有限连通图，

此外，上述极小化问题存在唯一的极小化流，它就是单位电流。

应用

定理. 设

是同一个图 的边上的两组电阻。若对所有 ，都有

则

推论.

• 添加一条边会减小有效电阻，因此会增大逃逸概率。
• 粘合顶点会减小有效电阻，因此会增大逃逸概率。

纳什—威廉姆斯不等式

定义. 若边集

满足：从 到 的每一条路径都包含 中的某条边，则称 是一个将 与 分离的边割集。

换言之，如果切断 中的所有边， 与 就不再连通。

定理（纳什—威廉姆斯不等式）. 若

是一族两两不相交、并且都将 与 分离的边割集，则

例

令 表示 的二维网格图。它的四个角点是

网格中的相邻关系为：坐标仅在一个分量上相差 的两个顶点由一条边连接。

定理. 令

并假设每条边的电阻均为 。则有效电阻满足

证明思路：

• 下界：应用纳什—威廉姆斯不等式；
• 上界：构造一个合适的单位流。

有效电阻

有效电阻在顶点集合上给出一个度量。

定理. 对任意顶点 ，均有三角不等式

麻省理工学院开放式课程