知识卡片
反向残余边允许撤回已有流
若原边 (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