知识卡片

普通读书笔记卡 · 3646.e.1.a.1

最大流等价于无增广路径

理解等级:中级

对流 f,残量网络记录每条边还能沿正向增加或沿反向撤回多少流;其中从源 s 到汇 t 的路径称为增广路径。以下三条件等价:f 是最大流;残量网络没有增广路径;存在源汇割 (S,T) 使 c(S,T)=|f|。

有增广路径就能增加流值,所以最大流不可能保留这种路径。反之,若无增广路,取残量图中从源点可达的顶点为 S;所有 S→T 原边必已饱和,所有 T→S 原边必为零流,否则相应残量边会让终点可达,于是跨割净流等于割容量。结合任意流不超过任意割容量,便得到最大流与最小割。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Theorem 24.6 (Max-flow min-cut theorem) If f is a flow in a flow network G = (V, E) with source s and sink t, then the following conditions are equivalent: f is a maximum flow in G. The residual network Gf contains no

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[25000,30000))。 - 结论依据:定理24.6逐向证明三条件等价,并构造无增广路径时的割。 - 原始内容:Theorem 24.6 (Max-flow min-cut theorem) If f is a flow in a flow network G = ( V , E ) with source s and sink t , then the following conditions are equivalent: f is a maximum flow in G . The residual network G f contains no