知识卡片
流增广把残量正反动作合并
设 f 是原网络中的流,f′ 是其残量网络中的流。在本章假设原网络不同时含 (u,v) 与 (v,u) 两条反向平行原边的模型下,增广运算 f↑f′ 对每条原边 (u,v) 定义为
(f↑f′)(u,v)=f(u,v)+f′(u,v)-f′(v,u)。
第二项把残量流沿原方向加入,第三项把沿反方向的残量流解释为撤回旧流。残量容量的定义保证结果不超过原边容量;f′ 自身的流守恒又保证合成后仍守恒。因此 f↑f′ 是合法流,且流值为 |f|+|f′|。
若一般模型允许两个方向都各有一条原边,就必须分别保存两条原边及其残余贡献,不能仅凭这一逐边简式把它们合并。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
The flow on (u, v) increases by f ′(u, v), but decreases by f ′(v, u) because pushing flow on the reverse edge in the residual network signifies decreasing the flow in the original network.
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[15000,20000))。
- 结论依据:原文解释同向增加、反向抵消;Art_P761 给出式(24.4),引理24.1用容量约束与流守恒证明合法性及流值相加。
- 原始内容:The flow on ( u , v ) increases by f ′( u , v ), but decreases by f ′( v , u ) because pushing flow on the reverse edge in the residual network signifies decreasing the flow in the original network.
- 公式图核读:`_epub-src/OEBPS/images/Art_P761.jpg` 的式(24.4)给出:原边 (u,v)∈E 时,(f↑f′)(u,v)=f(u,v)+f′(u,v)−f′(v,u);非原边取0。