图论（网络流量问题） _网络流量问题

最明显的流网络问题如下：
问题1：给定一个流量网络G =（V, E）, 最大流量问题是找到一个最大值的流量。
问题2：多个源和汇的最大流量问题与最大流量问题类似, 不同之处在于, 有一组{s1, s2, s3 … … . sn}源和一组{t1, t2, t3 … … … . tn}的水槽。
幸运的是, 这个问题比常规的最大流量还难。给定多个源和汇流网络G, 我们通过添加定义新的流网络G’

超级来源
超级沉
对于每个si, 添加容量为∞的边（s, si）, 然后
对于每个ti, 增加容量为∞的边（ti, t）

该图显示了多个源和汇流网络以及等效的单个源和汇流网络

文章图片
残留网络：残留网络由可以允许更多净流量的边缘组成。假设我们有一个流量网络G =（V, E）, 流量为s, 流量为t。令f为G中的一个流动, 并检验一对顶点u, v∈V。在超过容量c（u, v）之前, 我们可以从u推至v的额外净流量之和为（u , v）由

文章图片
【图论（网络流量问题）】当净流量f（u, v）为负时, 剩余容量cf（u, v）大于容量c（u, v）。
例如：如果c（u, v）= 16且f（u, v）= 16且f（u, v）= -4, 则剩余容量cf（u, v）为20。
给定一个流动网络G =（V, E）和一个流动f, 由f引起的G的剩余网络为Gf =（V, Ef）, 其中

文章图片
也就是说, 残差网络的每个边缘或残差边缘都可以接受严格的正净流量。
增强路径：给定流网络G =（V, E）和流f, 增强路径p是残留网络Gf中从s到t的简单路径。通过残差网络的解决方案, 增广路径上的每个边（u, v）都允许从u到v的一些额外正净流, 而不会违反边上的容量约束。
令G =（V, E）为流动f的流动网络。扩充路径p的剩余容量为