知识卡片

普通读书笔记卡 · 3646.d.3.a

流增广把残量正反动作合并

理解等级:中级

设 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′|。

若一般模型允许两个方向都各有一条原边,就必须分别保存两条原边及其残余贡献,不能仅凭这一逐边简式把它们合并。

这张卡片看不懂?

已有反馈 · 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。