CSCI3160 T10-proof 负环恢复证明

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T10-proof 负环恢复证明 · 原件 T10-proof-负环检测-未核-隐藏.pdf（本地课件） p.1–2 定位：T10 的两页配套证明；官网与 T10 p.33 将恢复负环部分列为不要求考试。

p.1 为什么追父亲有机会得到负环【新】

p.1 “Finding a Negative Cycle”

文件假设图强连通且已有负环。前七行是 Bellman–Ford 的普通轮次；第八至十行找到仍可改善的边 u→v，把 parent(v) 改为 u。注意第十行没有再改距离，故在新父边上保留严格不等式 dist(u)+w(u,v)<dist(v)。这个严格号将是证明环为负的来源。

Lemma 1 说，对于每条当前父边 p→x，始终有 dist(p)+w(p,x)≤dist(x)。普通设置父亲时二者相等；之后如果 p 的距离下降，左侧只会变小。若 x 的距离下降，会同时重新指定一条父边，重新建立这一性质。因此“父边对应相等”只在设置瞬间成立，不能在结尾对所有父边都写等号。

算一遍：T10 p.26 中 d=−30、g=−27，边 d→g 重 −3，左侧是 −33。将 parent(g) 指向 d 后有 −33<−27，这条父边严格；其他父边仍至少满足不严格的版本。

p.1 的 Lemma 2 要证明“只要形成父指针环，它在原图中的总权必负”。在这个环的父指针中，挑选最后一次被设置的那一条；就在设置之前，其他环边的父指针已经存在。被设置的边有严格改善，其他边满足 Lemma 1，把沿环的不等式相加，距离项抵消，环总重严格小于 0。若只写所有边都≤，最多得到总重≤0，排除不了零环。

补充：严格号并不是事后随便挑一条边。 若结尾只知道每条父边满足“不大于”，直接加起来只能证明环非正，不能区分负环与零环。要回到环上最后一次设置父亲的那个时刻：其余环父边此时已经存在，因此它们各自的不等式都可同时使用；当前设置来自严格改善，提供唯一需要的严格号。把这一时刻的距离逐项相加，才能得到严格负总重。不能混用不同时间的距离值来抵消。

自测：所有父边在各自设置时都曾经相等，能否相加得到环权为 0？

不能，因为“各自设置时”可能是多个不同时间；同一个点的距离已在其间降低，左边和右边不再是同一批数。证明必须固定同一个快照。结尾的≤不变量专门解决了父点后来变化的问题，而最后设置事件负责把≤加强为至少一个<。

对应完整恢复流程：先执行 |V|−1 轮普通松弛并保存父亲；再找一条仍严格可改善的 u→v，只设置 parent[v]=u，保留现有距离；令 S=[]、pos 为空映射、x=v；只要 x 未在 pos，就记录 pos[x]=|S|、向 S 追加 x，再令 x=parent[x]；首次重复 x 时，取 S[pos[x]:] 再追加 x，反转后输出。算法输入已保证存在负环，Lemma 3 保证这里不会遇到 nil；无需无限循环来实际检测重复。

Lemma 2 的正确边权和应为

w(u_1,u_x)+\sum_{i=1}^{x-1}w(u_{i+1},u_i)<0.

因为父边方向是 parent(ui)→ui，原页结尾的求和方向与上界索引也有笔误；按其列出的环边求和才与不等式对应。

p.2 追踪为什么不会走到空指针

Lemma 3 排除追踪在 nil 处停止。完成普通轮次后，强连通图的所有顶点距离有限；除源点之外，一个顶点从无穷变为有限时必设置过父指针，所以唯一可能保留 nil 的是源点。若追踪竟终止于仍为 nil 的源点，就得到一条不重复的源点到检测目标的有向路径，边数不超过顶点数减一。源点仍为 nil 也说明它未被严格改善，距离仍为 0。

沿这条路径累加父边不等式，且新设检测父边严格，推出“该路径总权小于目标的当前距离”。另一方面，Bellman–Ford 经过足够轮数，对每条至多顶点数减一条边的路径都保证“当前距离不大于该路径总权”。两结论矛盾。因此追踪必重复某个顶点；再用 Lemma 2 确定重复段确为负环。

原件还按逐轮归纳展开“长度不超过轮数的路径已经得到上界”，这里补齐这个版本。假设父链终止于 s，反向写路径 $z_0=s,z_1,\ldots,z_\ell=v$ ，令 $d_i=dist(z_i)$ 为当前快照。父边不变量给 $d_i\ge d_{i-1}+w(z_{i-1},z_i)$ ，且 $d_0=0$ 。第一轮已经扫描 s→z1，所以终值 $d_1\le w(s,z_1)$ ；上下界合并得等号，且第一轮末便已达到终值。若第 k 轮末 zk 已达到 dk，第 k+1 轮扫描 zk→z(k+1) 后有候选 $d_k+w(z_k,z_{k+1})$ ；终值只会更低，但父边下界又禁止更低，所以

d_{k+1}=d_k+w(z_k,z_{k+1})=\sum_{r=1}^{k+1}w(z_{r-1},z_r).

因此整条父路径至迟第 ℓ≤|V|−1 轮已经稳定，末轮检测边不可能严格改善，与选择该边矛盾。原页 Claim 第一项的上限应是当前 i，不能统一写成 ℓ；使用 r 作求和变量避免与外部 i 重名。

补充：原文的记号问题。 p.2 Lemma 2 最后一个不等式的右侧写成 dist(u1)，按父边 u1→ux 应为 dist(ux)，否则不能逐项抵消。原文 p.1 第 14 行说输出从 v 开始的 appendix，但循环终止时重复的是 parent(v)，不是当前 v；实现必须按“重复顶点在序列中首次出现的位置”截取。这里明确指出原文与可执行解释的区别，不把修正冒充原话。

算一遍：序列 g,d,c,b,a 后，a 的父亲 d 已在序列内。截取 d,c,b,a，再添 d，得到父链顺序 d,c,b,a,d；反转是 d,a,b,c,d，四条边总重 −6。若错从当前 a 截取，仅得 a,a，原图甚至不一定存在该自环。

初始化、普通松弛与末轮扫描加上父链追踪，总计为顶点数乘边数的主项，另有线性初始化和输出；不能把父链追踪写成额外一轮 Bellman–Ford。

考试角度：（B 级：T10 p.33 与教师官网说明）本文件服务于完整理解恢复算法，不作为官方要求考查的证明来标注。

本讲核心考点

父边保持不严格距离不等式，最后设定的环边提供严格号（p.1–2；C 级）。
有限距离、唯一可能空父亲、路径边数上界共同保证追踪一定成环（p.2；C 级）。
须截取首次重复顶点所在的后缀，再反转为有向环（p.1–2；B 级：配套说明列为非考试内容）。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：T10-proof-负环检测-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。