知识卡片
增广后总流严格增加
若残量图有增广路径 p,其瓶颈容量 c_f(p)>0;沿该路径增广后仍是合法流,而且流值从 |f| 增至 |f|+c_f(p)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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