图的导通率

图的导通率（graph conductance）比较一条切割跨出去的边权与较小一侧的度数总量。它寻找相对于内部规模而言难以离开的顶点集合。分母按度计量，因而不同于按顶点数归一化的边扩张率，也不同于电路中某两端点间的等效电导。

四顶点路径中的瓶颈

取无权路径 $1-2-3-4$，度为 $(1,2,2,1)$。集合 $S=\{1,2\}$ 与补集之间只有边23，总跨边权为一；两侧度数和都为三，因此该切割的导通率是 $1/3$。只取端点集合 $\{1\}$ 时，跨边权为一，较小度数和为一，比例反而是一。

每侧的内部边贡献两个度，跨割边贡献一个度。因此左侧体积是三，不是二个顶点或一条内部边。

定义、体积与无量纲尺度

先设图有限、无向、无自环、边权非负，至少有两个顶点且每个顶点度 $d_i>0$。记 $$\mathrm{vol}(S)=\sum _{i\in S}{d}_i,c(S)=\sum _{i\in S,j\notin S}{w}_{ij}.$$ 每条跨割边只计一次。对非空真子集定义 $$\varphi (S)=\frac{c(S)}{min\{\mathrm{vol}(S),\mathrm{vol}(V\setminus S)\}},\varphi (G)=\underset{\varnothing \ne S\ne V}{min}\varphi (S).$$ 也可以只在 $0<\mathrm{vol}(S)\le \mathrm{vol}(V)/2$ 的集合上最小化 $c(S)/\mathrm{vol}(S)$。较小侧所有跨边权已包含在该侧的度数和中，所以 $0\le \varphi (G)\le 1$。把全部边权乘同一个正常数，分子分母同比例变化，导通率不变。

主例全部切割可不重不漏地用包含顶点一的七个集合代表：$\{1\},\{1,2\},\{1,3\},\{1,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\}$。对应比例依次为 $1,1/3,1,1,1,1,1$，所以图的最小导通率确为 $1/3$，不是仅找到一个候选上界。

与随机游走和不连通图的关系

按边权选择下一邻点的随机游走有平稳权重 ${\pi }_i=d_i/\mathrm{vol}(V)$。如果按这一分布条件化在 S 内，起点 i 的概率为 $d_i/\mathrm{vol}(S)$，下一步离开 S 的概率就是 $$\sum _{i\in S}\frac{d_i}{\mathrm{vol}(S)}\sum _{j\notin S}\frac{w_{ij}}{d_i}=\frac{c(S)}{\mathrm{vol}(S)}.$$ 这给出小侧导通率的“一步流失比例”解释。它不是说任意起点的离开概率都相同；端点一的下一步必然仍在主例的 S 内。

若所有度正而图不连通，取一个连通分量便有 $c(S)=0$，所以导通率为零。若图连通，每个非平凡切割都有正跨边权，而集合有限，所以最小值为正。有孤立点时可先删去它们，在正度诱导图上使用本篇定义；若正度部分为空，则不定义图导通率。这个约定下孤立点不影响正度部分的导通率，却影响整个图是否连通，故前述充要关系不能未经限定搬到含孤立点的图上。

归一化谱给出的下界

令 ${\nu }_2$ 为归一化拉普拉斯矩阵的第二小特征值，在本节的正度条件下有 $$\frac{{\nu }_2}{2}\le \varphi (G)\le \sqrt{2{\nu }_2}.$$ 先证明左侧。广义瑞利商表示为 ${\nu }_2=\underset{f\ne 0,\sum _i{d}_i{f}_i=0}{min}(f^{𝖳}Lf)/(\sum _i{d}_i{f}_i^2)$。给切割两侧体积记为 $a\le b$，在小侧取 $f_i=1/a$、大侧取 $f_i=-1/b$。它满足加权零均值，其商为 $$c(S)(1/a+1/b)\le 2c(S)/a=2\varphi (S).$$ 因此 ${\nu }_2\le 2\varphi (S)$ 对所有切割成立，取最小值得到下界。

阈值切割给出的上界证明

若图不连通，两侧都是零，上界已成立。对连通图取第二广义特征向量 f，满足 $Lf={\nu }_{2}Df$、$\sum _i{d}_i{f}_i=0$。选择 f 的符号，使正值顶点的体积不超过全图一半，并令 $u_i=max(f_i,0)$。正负值均存在，故 u 非零；两种符号的正支持不交，总体积不超过全图，至少一种符合要求。

记 $A=\sum _{\{i,j\}}{w}_{ij}(u_i-u_j{)}^2$、$B=\sum _i{d}_i{u}_i^2$。正部函数单调且变化幅度不超过原差，所以逐边有 $(u_i-u_j{)}^2\le (u_i-u_j)(f_i-f_j)$。求和并用特征方程得到 $A\le u^{𝖳}Lf={\nu }_2{u}^{𝖳}Df={\nu }_{2}B$。

对阈值 $t\ge 0$ 定义 $S_t=\{i:u_i^2>t\}$，其非空时体积不超过一半。逐个顶点、逐条边积分，有 $${\int }_0^{\mathrm{\infty }}\mathrm{vol}(S_t)\mathrm{d}t=B,{\int }_0^{\mathrm{\infty }}c(S_t)\mathrm{d}t=\sum _{\{i,j\}}{w}_{ij}|u_i^2-u_j^2|.$$ 第一式因为顶点 i 在长度为 $u_i^2$ 的阈值区间内被计入；第二式因为边跨割恰发生在两端平方值之间。至少有一个非空阈值集合的导通率不超过这两个积分的比，否则积分后仍会严格更大。

最后用柯西不等式与 $(u_i+u_j{)}^2\le 2(u_i^2+u_j^2)$，得到 $$\sum _{\{i,j\}}{w}_{ij}|u_i^2-u_j^2|\le \sqrt{A\sum _{\{i,j\}}{w}_{ij}(u_i+u_j{)}^2}\le \sqrt{2AB}.$$ 所以某个阈值切割满足 $\varphi (S_t)\le \sqrt{2A/B}\le \sqrt{2{\nu }_2}$，从而完成上界证明。这里每条边在求和中仍只出现一次。

主例的归一化特征值为 $0,1/2,3/2,2$，可由矩阵直接验算。例如广义向量 $(1,1/2,-1/2,-1)$ 对应 ${\nu }_2=1/2$；另三个广义特征向量可取 $(1,1,1,1)$、$(1,-1/2,-1/2,1)$、$(1,-1,1,-1)$。故谱界给出 $1/4\le 1/3\le 1$，并不声称精确相等。

权重变式与指标限制

把主例两端边权保留为一，中间桥权改成 $\epsilon >0$。中间切割的比例变为 $\epsilon /(2+\epsilon )$。全部七种代表切割中，其余六个比例仍为一，所以这也是图导通率的精确值；当桥权趋零时，它趋零。若所有边同时乘十，比例却不变，这说明瓶颈比较的是相对流量。

导通率较小只表明存在一个相对弱连接集合，不自动确定它的实际含义，也不说明某个随意阈值都能找到最优切割。谱上界证明保证存在合适阈值；计算时仍需检查阈值产生的切割。混用有向流量、负权或把体积换成顶点数，会改变问题与谱界条件。