费德勒向量

费德勒向量是对一个连通图想如何被一分为二的最佳一维概括。它给每个节点赋一个实数，使联系紧密的节点取到相近的值，于是在零处切分（正对负）就沿图最弱的接缝把它分开。

形式上，把拉普拉斯矩阵的特征值排序为 0 = lambda_1 <= lambda_2 <= ...。费德勒向量是第二小特征值 lambda_2 对应的特征向量，lambda_2 称为代数连通度。它与平凡的全一特征向量正交，故其分量必含两种符号，而符号模式诱导出一个平衡的二分划分。

lambda_2 本身衡量图的连通好坏：它恰在图连通时为正，值越大表示图越难被断开（一个稳健、类扩张子的网络），而接近零的 lambda_2 标志着图有一处细瓶颈正等着被切。

为何重要：费德勒向量是图二分、网格与电路划分的主力，也是递归谱聚类的第一步。警示：它给出的是松弛解，而非精确最小割（后者 NP 难），故取整后的划分是近最优而非保证最优；在有多个相当瓶颈的图上，单个向量无法把它们尽数捕获。