图论：网络流量问题

最明显的流网络问题如下：

问题1：给定一个流量网络G =（V, E）, 最大流量问题是找到一个最大值的流量。

问题2：多个源和汇的最大流量问题与最大流量问题类似, 不同之处在于, 有一组{s1, s2, s3 ……. sn}源和一组{t1, t2, t3 ………. tn}的水槽。

幸运的是, 这个问题比常规的最大流量还难。给定多个源和汇流网络G, 我们通过添加定义新的流网络G’

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

残留网络：残留网络由可以允许更多净流量的边缘组成。假设我们有一个流量网络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的剩余容量为

剩余容量是可通过扩充路径推动的最大流量。如果存在增广路径, 则其上的每个边都具有正容量。我们将利用这一事实来计算流量网络中的最大流量。