知识卡片
割容量为任意流的上界
割 (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)。
第一步利用流量非负,删去会降低净值的后向流;第二步利用逐边容量约束。由于此式对每个源汇割都成立,最小割容量给出最大流的全局上界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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, ▪