知识卡片

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

增广后总流严格增加

理解等级:中级

若残量图有增广路径 p,其瓶颈容量 c_f(p)>0;沿该路径增广后仍是合法流,而且流值从 |f| 增至 |f|+c_f(p)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Corollary 24.3 Let G = (V, E) be a flow network, let f be a flow in G, and let p be an augmenting path in Gf. Let fp be defined as in equation (24.7), and suppose that f is augmented by fp. Then the function f ↑ f

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[20000,25000))。 - 结论依据:推论24.3结合残量路径流与合成引理得出严格增量。 - 原始内容:Corollary 24.3 Let G = ( V , E ) be a flow network, let f be a flow in G , and let p be an augmenting path in G f . Let f p be defined as in equation (24.7), and suppose that f is augmented by f p . Then the function f ↑ f