代数连通度

代数连通度（algebraic connectivity）是无向非负加权图的未归一化拉普拉斯矩阵第二小特征值，通常记为 ${\lambda }_2$。对至少两个顶点的图，它为正当且仅当正权边组成的图连通；较小的值意味着存在某种变化较慢、边差能量较低的非恒定赋值。

路径为何得到数值一

路径 $1-2-3$ 的拉普拉斯矩阵为 $$L=\left(\begin{array}{ccc}1& -1& 0\\ -1& 2& -1\\ 0& -1& 1\end{array}\right).$$ 向量 $(1,1,1)$、$(1,0,-1)$、$(1,-2,1)$ 分别对应零、一、三三个特征值，故代数连通度为一。若把三点都连接成三角形，则 $L=3I-J$，其中 J 的元素全为一。在与常数向量正交的平面上 J 为零，两个剩余特征值都为三，代数连通度增至三。

新增边约束两端相反的赋值，原来的低能量模式不再同样便宜。

零均值约束与最小能量

设图有 $n\ge 2$ 个顶点，边权非负、无向且无自环，$L=D-A$。把实特征值从小到大列为 $0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$。其变分表达为 $${\lambda }_2=\underset{x\ne 0,\sum _i{x}_i=0}{min}\frac{\sum _{\{i,j\}\in E}{w}_{ij}(x_i-x_j{)}^2}{\sum _i{x}_i^2}.$$ 零均值排除处处相同的无信息赋值；分母固定尺度，否则把所有值缩到零就能任意减小分子。

这个公式可从谱分解直接证明。取第一单位特征向量为 $\mathrm{𝟏}/\sqrt{n}$，补成 L 的正交特征向量组。满足零均值的 x 不含第一方向，写成 $x=\sum _{k=2}^n{a}_k{v}_k$，其商为 $\sum _{k=2}^n{\lambda }_k{a}_k^2/\sum _{k=2}^n{a}_k^2$，至少为 ${\lambda }_2$，取第二特征向量达到等号。这个证明也允许零特征值有重数。

若图连通，边差能量为零只能使 x 为常数；同时零均值便只能为零。单位球面与零均值空间的交紧致，能量在其上处处正，最小值因此为正。若图不连通，任选一个非空分量 S，在 S 上赋 $1/|S|$，其余顶点赋 $-1/(n-|S|)$。该向量非零、总和零、各边两端相同，所以能量为零，得到 ${\lambda }_2=0$。这证明了连通性的充要关系，而不是只给出一个方向。

切割产生一个可算上界

对任意非空真子集 S，记其顶点数为 s，跨越 S 与补集的边权和为 $c(S)$。在 S 上赋 $1/s$、补集上赋 $-1/(n-s)$，边差仅在跨割边非零。该试验向量的分子为 $c(S)(1/s+1/(n-s){)}^2$，分母为 $1/s+1/(n-s)$，故 $${\lambda }_2\le \frac{nc(S)}{s(n-s)}.$$ 因此把两个规模不小的部分仅用很小总权重连接，会给出较小的代数连通度上界。这里分母是顶点数的乘积，不是两侧度数和的乘积。

例如两个各含三点的无权三角形之间只加一条权为 $\epsilon >0$ 的桥边，取 S 为一侧三角形，得到 $0<{\lambda }_2\le 2\epsilon /3$。桥很弱时图仍连通，但数值可以任意接近零；仅说“连通”无法表达这种差异。若桥权变为零，图断开，代数连通度恰为零。

试验向量在每组内保持常数，只有桥边贡献能量；其瑞利商为2ε/3，给出第二特征值的上界。

加边变式与尺度限制

在同一顶点集上增加一条权为 $t\ge 0$ 的边 uv，任意向量的能量增加 $t(x_u-x_v{)}^2\ge 0$。在相同零均值单位球面上取最小值，便证明新 ${\lambda }_2$ 不小于旧值。主例路径添成三角形是严格增大的一个实例；增大不一定严格，因为某个最小模式可能在新增边两端原本取相同值。

变式考虑只有两个顶点、一条权为 w 的边。矩阵为 $w\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$，代数连通度是 $2w$。把所有边权乘十，代数连通度也乘十，即使图的连接方式完全一样。因此不同权重单位下的数值不能直接比较。归一化拉普拉斯矩阵的第二特征值还使用不同分母，也不应默认称为这里同一个数。

给图增加一个孤立顶点改变了顶点集，会使代数连通度降为零；这不与“固定顶点集的非负加边单调性”矛盾。只有一个顶点时没有第二个特征值，本篇不另外定义数值。负权或有向非对称矩阵也超出前面的非负能量与正交谱论证。