知识卡片

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

正向残余容量是未用额度

理解等级:中级
  • 对原边 (u,v),c(u,v) 是容量,f(u,v) 是当前流量。若 f(u,v)<c(u,v),残量网络保留同向边,残余容量为 c_f(u,v)=c(u,v)-f(u,v);
  • 边已满载时残余容量为 0,因而不出现在残量图中。

补充教学演示:容量为 10、已送 6 单位流时,同向还可增加 4 单位;若已送到 10,便不能再沿同向增广。残量容量描述的是“在当前流基础上还能怎么改”,并不是原网络的新容量。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      If that value is positive, that edge goes into Gf with a “residual capacity” of cf (u, v) = c(u, v) − f (u, v). The only edges of G that belong to Gf are those that can admit more flow. Those edges (u, v)

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[15000,20000))。 - 结论依据:原文给出同向残余容量及零容量边不保留的条件;数值代入为补充教学演示。 - 原始内容:If that value is positive, that edge goes into G f with a “residual capacity” of c f ( u , v ) = c ( u , v ) − f ( u , v ). The only edges of G that belong to G f are those that can admit more flow. Those edges ( u , v )