知识卡片

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

割容量为任意流的上界

理解等级:中级

割 (S,T) 的容量只统计从源侧到汇侧的原边:c(S,T)=Σ_{u∈S,v∈T}c(u,v)。任意流值等于跨割净流,故

|f|=Σ_{S→T}f(u,v)−Σ_{T→S}f(u,v)≤Σ_{S→T}f(u,v)≤Σ_{S→T}c(u,v)=c(S,T)。

第一步利用流量非负,删去会降低净值的后向流;第二步利用逐边容量约束。由于此式对每个源汇割都成立,最小割容量给出最大流的全局上界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Corollary 24.5 The value of any flow f in a flow network G is bounded from above by the capacity of any cut of G. Proof Let (S, T) be any cut of G and let f be any flow. By Lemma 24.4 and the capacity constraint, ▪

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[25000,30000))。 - 结论依据:推论24.5结合净流等于流值与容量约束。 - 原始内容:Corollary 24.5 The value of any flow f in a flow network G is bounded from above by the capacity of any cut of G . Proof Let ( S , T ) be any cut of G and let f be any flow. By Lemma 24.4 and the capacity constraint, ▪