白板上的旧箭头被擦掉,只剩一道灰印。
`b_e^tp_Eb_e → Δ_e`
单个Fiedler特征空间能量曾被他们寄望为删边后谱隙下降的预测器。重根基底旋转、十四点对抗图和远处增长图族已经把这个愿望拆得很干净。
林一重新写下目标边向量`b_e=e_u-e_v`,在右边画出三只盒子。
第一只装第二特征空间上的能量。
第二只装紧邻第二特征值的谱层能量。
第三只装更高谱层的剩余能量。
“局部指哪里?”周锡京问。
“能量都来自同一条目标边。”林一说,“层次按谱位置分,不按图上的半径分。”
她在标题旁补了一句:边局部,谱分层。随后把“有限邻域方法”移进另一张路线图,免得两种局部混成一个概念。
对有限无向连通图`G`,组合拉普拉斯的特征值依次为
`0=λ?<λ?<λ?≤…≤λ_n`。
他们先把`λ?`限定为单重。单位特征向量记作`v?`,目标边在这一层的能量是
`a=(b_e^tv?)2`。
再把`i≥3`的特征向量按离`λ?`的距离分组。各`I_j`组成`{3,…,n}`的一个分划,同一重特征值的完整特征空间归入同一层。第`j`层离`λ?`的已知下界为`g_j>0`,目标边投影能量为
`q_j=Σ_{i∈I_j}(b_e^tv_i)2`。
所有`a、q_j、g_j`都从删边前的谱分解计算。
周锡京把三层改成五层,再改成十层。分得越细,每层分母越接近真实特征值,证书更紧;分得越粗,计算与展示更便宜。它们回答的是同一条边的能量落在谱的哪些位置。
她故意把一份十层证书压回三层。屏幕上的文件从两页缩成半页,`R`却从0.58涨到0.71,最后的上界随之变宽。林一又将三个相距很远的高阶特征值塞进同一盒,最小间隔替整层承担分母,原本很小的高层能量被放大。
“压缩有代价。”周锡京说。
林一在三层图旁写下损失值。以后每次展示粗证书,都必须同时保留逐特征值版本作为核验基线;任何人为分层方案都要记录区间端点,不能只交一张颜色好看的柱状图。
“先跑旧反例。”林一说。
十四点两张图在`a`上仍然接近,分层后的`q_j/g_j`却从第二层开始分开。过去被压成一个数的信息,终于在证书里露出不同形状。
另一组对抗图仍很难看。它们的前两层近似一致,差异直到高谱层才出现。如果只保留三层粗分组,上界会松得几乎没有用途。
林一把这组图放到第一页。多层证书可以减少信息损失,却没有保证每次都给出锋利结果。
邱逸真到讨论室时,程序已经生成二十七份分层证书。
“命题。”他说。
林一把条件逐项投上屏幕:`e`是删后保持连通的非桥边;`λ?`单重;用删边前正交特征基展开`b_e`;各谱层有明确的间隔下界`g_j`。定义
`R=Σ_j q_j/g_j`。
若`R<1`,候选结论为
`a ≤ Δ_e ≤ a/(1-R)`。
左端是他们已经证明的Rayleigh下界。新工作在右端,而且右端只使用删边前的可计算量。
邱逸真的短钢尺压住`R<1`。
“少了它会怎样?”
“分母失去正性,推导不给有限上界。”
“是定理失效,还是这张证书失效?”
林一停了一下。
“当前只能说证书失效。真实下降仍然存在。”
他把“失败”改成“无认证”。
证明从秩一删边开始:
`L_{G-e}=L_G-b_eb_e^t`。
若`a>0`,删边后的第二特征值写成`μ=λ?-Δ_e`。在与全一向量正交的空间里,秩一扰动的世俗方程给出
`1=a/Δ_e+Σ_{i≥3}(b_e^tv_i)2/(λ_i-λ?+Δ_e)`。
每个谱层内,`λ_i-λ?+Δ_e≥g_j`。于是余项不超过
`Σ_j q_j/g_j=R`。
方程两边同时扣掉余项,得到
`1-R≤a/Δ_e`,也就是
`Δ_e≤a/(1-R)`。
若`a=0`,`v?`在删边后保持为特征向量。此时高谱块的精确余项
`S?=Σ_{i≥3}(b_e^tv_i)2/(λ_i-λ?)`
满足`S?≤R<1`,高谱块减去该秩一项后仍为正定,不会越过`λ?`产生新根,因此下降量为零,同一结论仍成立。
邱逸真没有让他庆祝。
“世俗方程在哪些情况下能这样写?”
“删边后目标分支位于`λ?`下方,按删前正交特征基展开;投影为零的项直接消失,`a=0`另用高谱块正定性处理。”
“重根?”
“暂不覆盖。现在的`λ?<λ?`是明写条件。”
“删边后仍连通?”
“明写。桥边不进入对象集。”
“`g_j`怎么取?”
“每层特征值与`λ?`距离的下界。逐特征值分层时可直接取真实间隔,粗分层则取该层最小间隔。”
邱逸真把短钢尺移开。
“现场验。”
正式跑程序前,他又让林一关掉屏幕。
“你先解释为什么多层会比一个总余量有用。”
林一在纸上画了两个谱层。相同的投影能量若落在离`λ?`很近的位置,分母小,对扰动根的位置影响大;若落在很远的高谱层,分母大,贡献会被压低。把所有余量只加成`2-a`,就丢掉了它们离目标特征值有多远。
“所以`q_j`是分子,`g_j`是位置。”
“位置下界。”邱逸真纠正。
“对,只取每层能够保证的最近距离。这样会放宽结果,但不会把上界写窄。”
邱逸真让他在页边写下这句。一个“位置”与一个“位置下界”,差的是整条不等号方向。
周锡京先调出三角形。它的第二特征值为重根,程序直接返回“条件不满足”,没有硬算一个绿色答案。
四环同样被重根挡住。
第三张是第二特征值单重的带弦六点图。程序从删边前谱分解得到`a`与四层`q_j`,`R=0.63`。认证区间包住真实下降,上界偏松,却有限且方向正确。
周锡京把浮点结果切到高精度,再用有理区间包住每个输入。`R`的上端仍低于一,分母的正性无需依赖显示器上被四舍五入的0.63。她把普通双精度结果留作探索,把区间版本放进正式证书。
林一逐项点开输入来源。`a`来自删前第二特征向量,四组`q_j`来自删前谱投影,`g_j`来自删前特征值间隔;删边后的真实下降只出现在验证栏,不参与上界计算。他让程序把验证栏整个隐藏,又重算一次,输出没有变化。
她再加载一个`R=1.08`的近瓶颈样本。程序显示“无认证”,真实下降仍由完整计算另栏给出。
“这次没有把算不出的写成零。”她说。
林一把两张结果并排:一张通过,一张无认证。随后关闭删边后谱分解,只用删边前输入重跑。通过样本的上界保持不变。
讨论室里终于响起掌声。
林一握拳砸了一下桌面。这个界不锋利,覆盖的图也窄,可它第一次把单项预测改成了分层证书,并且在真正删边之前就能计算。
程野从隔壁探进头,只看见满屏符号,问他们有没有又把命题缩没。周锡京把通过样本和无认证样本各打印一张塞给他。
“左边能在删边前给上界,右边诚实闭嘴。”
程野盯了半分钟,指着左页最下方的区间问:“真值在哪?”
“封在验证页。”林一说,“你先看证书有没有偷读。”
三个人重新按输入清单检查一遍。确认删后特征值只用于末端对照后,程野才把左页举起来,朝门外喊了一声“过了”。走廊里有人跟着鼓掌,声音沿着门缝涌进来。
邱逸真让他把掌声听完,才问:“叫什么?”
“简单谱隙下的分层边能量界。”
“别加‘主’。”
“不加。”
周锡京将证明页放到第二页,第一页继续保留重根、`R≥1`和高谱层差异晚出现的失败对象。夏雨杭赶到后,从头核对量词,在“单重”与“删边前”下面各画一道粗线。
“这两处丢一个,整条声明都会变。”他说。
林一重新口述一遍,没有漏字。
他们把程序输出改成四种状态:已认证、无认证、重根超出范围、输入不足。绿色只给第一种。代码测试加入逐特征值细分与三层粗分两套结果,前者负责紧界,后者负责展示信息压缩的代价。
林一又加了一项反向测试:故意打乱谱层编号,程序必须拒绝;把`g_j`误填成层内最大间隔,程序同样拒绝;只要`R`的认证上端碰到一,状态就从绿色切成无认证。三种错误都被写进测试名里,防止以后为了得到更漂亮的界悄悄放松输入。
庆祝只持续了十分钟。蛋糕纸托还没收走,周锡京就把重根样本重新拖到中央。
“研讨会要是问多重特征值呢?”
“回答当前没有。”林一说,“然后把完整特征空间版本列成下一项。”
一周后,第十四天下午,训练组发来固化结束的会诊通知。右侧小腿连续多日处于个人带,零至三十米动作稳定,下一次跑道任务将把距离拉到一百二十米。
林一保存证明,文件名里写着`simple-gap`。
数学把能量拆进不同谱层,跑道则要看新动作经过九十米以后,哪一层先断。