知识卡片

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

增广路径是残量图源汇路

理解等级:中级

增广路径是残量网络中从源点 s 到汇点 t 的一条简单路径。路径上的每条边都表示当前流还能沿该方向调整的额度。

沿路径统一增加同一流量才能保持中间顶点的流守恒,因此最多只能增加路径上最小的残余容量,即瓶颈容量 c_f(p)=min{c_f(u,v):(u,v)∈p}。

补充教学演示:一条增广路径的三条边残余容量依次为 5、2、7,则最多增广 2;增广后第二条边饱和,这条路径也就不能继续使用。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      an augmenting path p is a simple path from s to t in the residual network Gf. By the definition of the residual network, the flow on an edge (u, v) of an augmenting path may increase by up to cf (u, v) without

    参考来源

    - 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[20000,25000))。 - 结论依据:原文定义增广路径和路径残余容量最小值;数值代入为补充教学演示。 - 原始内容:an augmenting path p is a simple path from s to t in the residual network G f . By the definition of the residual network, the flow on an edge ( u , v ) of an augmenting path may increase by up to c f ( u , v ) without