4.2最大流及其算法 ·就只有一个发点和一个收点的网络而言,最大流 题就是在一个有容量的网络中从发点到收点找出 条可以运送最大数量的单位流量的路径,而且不得 超过弧的容量 最大流问题的算法是由Ford和 Fulkerson于1957最早提 出的,其基本概念比较筒单,即从某个初始流开始, 重复地增加流的值到不能再改进为止,则最后所得的 流将是一个最大流。为此,不妨将每条边上的流量设 置为0作为初始流量。为了增加给定流量的值,我们 必须找出从发点到收点的一条路并沿这条路增加流量 2021/12/10 重庆邮电大学 理学 16 院
4.2 最大流及其算法 • 就只有一个发点和一个收点的网络而言，最大流问 题就是在一个有容量的网络中从发点到收点找出一 条可以运送最大数量的单位流量的路径，而且不得 超过弧的容量。 2021/12/10 重庆邮电大学 理学 院 16 • 最大流问题的算法是由Ford和Fulkerson于1957最早提 出的，其基本概念比较简单，即从某个初始流开始， 重复地增加流的值到不能再改进为止，则最后所得的 流将是一个最大流。为此，不妨将每条边上的流量设 置为0作为初始流量。为了增加给定流量的值，我们 必须找出从发点到收点的一条路并沿这条路增加流量
没N三<N,E,C>是具有发点S、收点和容量C的 个网络,P=ve1v1e212…1n-1envn,(其中vo=S, n=t)是网络N中从S到t的一条路。 规定路的方向由发点S指向收点t,则P中与规定方向 致的弧称为正向弧,所有正向弧的集合记为P+ °与规定方向相反的孤称为反向弧,所有反向弧的集合 记为Pˉ。显然,P和Pˉ中可能有一个是空集。 2021/12/10 重庆邮电大学 理学 17 院
2021/12/10 重庆邮电大学 理学 院 17
定义1设F是网络N=<N,E,C>的一个可行流,P是 条从S到t路,则P上满足下列条件之一的弧<v,v>称 增广孤。 (1)<vv>∈P+,且F<C;即<v;v>为非饱和弧; (2)<vv>∈Pˉ,且F>0即<vv>为非空弧 若P上任意一条弧<vv>都满足(1)或(2),则称P 是一条F非饱和路径。一条S到t的F非饱和路径称为F可增 长路径或F增广路。 5.4 74 6,1 5.4 10.3 54 202l/12/10 重庆邮电大学 理学院 18
2021/12/10 重庆邮电大学 理学院 18 10,3 5,1 7,4 5,4 9,5 5,4 6,1 5,4
·如果一条路P上的每条弧的方向都是正的,并且 条弧上流量小于其容量,就可能增加流量值,其 大增值为:min(Ca ;,1;)∈P 例如,如图4.21(a所示为从发点S到收点【的一条路P,路P上每条弧都是正向的。则路 P上的流最大可以增加1,如图42.1(b所示。 3.1 2.1 3.2 (a) 5.2 5.0 4.2 d) 6.5 5,3V242382 6,6V15,2124 8.3 2021/12/10 图421增广路上流量的增加理学院 19
2021/12/10 重庆邮电大学 理学院 19 例如，如图 4.2.1 (a)所示为从发点 s 到收点t 的一条路 P，路 P 上每条弧都是正向的。则路 P 上的流最大可以增加 1，如图 4.2.1 (b)所示。 3,1 2,1 4,1 (a) 3,3 5,2 4,4 (c) 3,1 5,0 4,2 (d ) 6,6 5,2 4,3 8,3 3,2 2,2 4,2 (b) 6,5 5,3 4,2 8,2 (e) (f ) 图 4.2.1 增广路上流量的增加
3,2 3 244 5.0 (d) 6.5 4.2 8,2 V5,2V24,3 8,3 图42.1增广路上流量的增加 ·如果一条从发点S到收点路P上的每条弧的方向都是 负的,则这条路上毎条孤中的流都可以减少,形成 s到t的较少的流,因而就形成从s到t较大的流。这条 P上的流最大可以减少为:min。F ;)∈P 2021/12/10 重庆邮电大学 理学院
3,1 2,1 4,1 (a) 3,3 5,2 4,4 (c) 3,1 5,0 4,2 (d ) 6,6 5,2 4,3 8,3 3,2 2,2 4,2 (b) 6,5 5,3 4,2 8,2 (e) (f ) 图 4.2.1 增广路上流量的增加 2021/12/10 重庆邮电大学 理学院 20