知识卡片

普通读书笔记卡 · 3646.d.2

反向残余边允许撤回已有流

理解等级:中级

若原边 (u,v) 已送流量 f(u,v)>0,残量图可出现反向边 (v,u),其残余容量为 c_f(v,u)=f(u,v)。沿反向边送流并非在原网络凭空新增一条边,而是减少 (u,v) 上的已有流量,以便把这部分容量重新分配给别的路径。

补充教学演示:若 (u,v) 已送 6 单位流,反向最多可送 6;反向增广 2 后,原边流量变为 4。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第24章 最大流 · 查看原书依据

      the residual network Gf contains an edge (v, u) with residual capacity cf (v, u) = f (u, v)—that is, an edge that can admit flow in the opposite direction to (u, v), at most canceling out the flow on (u, v

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[15000,20000))。 - 结论依据:原文明确反向残余边容量等于原边流量,并解释取消流量;数值代入为补充教学演示。 - 原始内容:the residual network G f contains an edge ( v , u ) with residual capacity c f ( v , u ) = f ( u , v )—that is, an edge that can admit flow in the opposite direction to ( u , v ), at most canceling out the flow on ( u , v