例:一个网络流图上的可行流: a(蓉量 容许流ft (4,3 (3,2) (2,1)((3,0) (3,2) b 4,4 (4,3) c(2,2) 26
26 例：一个网络流图上的可行流： s t a b c d (4,3) (4,3) (3,2) (2,1) (3,0) (2,2) (2,2) (4,4) (1,1) (3,2) (2,2) 容量 容许流fat
■整个流网络G的流量为: f=∑fs,)(v∈V)或=∑fu,u∈V 即从源出发的所有流的总和 ■[三个重要性质 或到达汇的所有流的总和 口容量约束: 对所有的uv∈V,要求f(u)≤=c(u,y); 口平衡约束(反对称性): 对所有的uv∈V,要求uv)=,u);流量平衡方程 口流守恒性: 对所有u∈V{s,+,要求∑f(uv)=0(∈V)
27 ◼ 整个流网络G的流量为： |f|=∑f(s,v)(v∈V) 或 |f|=∑f(u,t)(u∈V) ◼ 『三个重要性质』 容量约束： ◼ 对所有的u,v∈V，要求f(u,v)<=c(u,v)； 平衡约束（反对称性）： ◼ 对所有的u,v∈V，要求f(u,v)=-f(v,u)； 流守恒性： ◼ 对所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。 流量平衡方程 即从源出发的所有流的总和 或到达汇的所有流的总和
■根据各点流量守恒的关系,可得下列各式: sattsb+tsc=W a fbt+fat=W 3 sa ab (3) 3 fSb+fcb +fab=+fbt+fd (4) SC (5) (6) c 2 bd cd 0≤f6a≤4,0≤fb≤3,0≤f≤4,0≤fab≤2,0sfba≤3, 0≤f≤3,0≤f≤2,0≤f≤2,0≤f≤1,0≤f cd ≤2 0≤f6≤2,W20 28
28 ◼ 根据各点流量守恒的关系，可得下列各式： fsa+fsb+fsc=w (1) fat+fbt+fdt=w (2) fsa+fba＝fat+fab (3) fsb+fcb+fab＝fba+fbt+fbd (4) fsc ＝fcb+fcd (5) fbd+fcd＝fdt (6) 0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3， 0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2， 0≤fdt≤2，w≥0 s t a b c d 4 4 3 2 3 2 2 1 4 3 2
2最大流 对于一个流网络G=(V,E,c),在其可行流中,流量最大的 一个流就是最大流; 注意:最大流可能不止一个。 3 4 s 6 5)t 5)t 3 3 一个可行流 个可行流(也是最大流)
29 2.最大流 ◼ 对于一个流网络G=(V,E,c)，在其可行流中，流量最大的 一个流就是最大流； ◼ 注意： 最大流可能不止一个。 一个可行流 一个可行流（也是最大流） 1 2 3 4 5 4 3 2 6 2 5 4 1 1 3 4 3 s t 1 2 3 4 5 4 3 2 6 4 5 4 3 1 3 4 3 s t
残留网络 对于给定的一个流网络G及其上的一个流foW,网 络G关于流foW的残留网络G*与G有相同的顶点集 而网络G中的每一条边对应于G*中的1条边或 2条边。 ■设(,W)是G的一条边: 口当fowW)>0时,(w,)是G中的一条边,该边的容量 为 cap*(W, v)=fW(v,w);注意:反向边 口当fow(,w)<cap(v,w)时,(,w)是G*中的一条边,该边 的容量为capw)=cap(v,W)fWw(W) 注意:两个条件可能同时都成 注意:正向边 立,因此就对应两条边。 30
30 残留网络 ◼ 对于给定的一个流网络G及其上的一个流flow，网 络G关于流flow的残留网络G*与G有相同的顶点集 V，而网络G中的每一条边对应于G*中的1条边或 2条边。 ◼ 设(v,w)是G的一条边： 当flow(v,w)>0时，(w,v)是G*中的一条边，该边的容量 为cap*(w,v)=flow(v,w)； 当flow(v,w)<cap(v,w)时，(v,w)是G*中的一条边，该边 的容量为cap*(v,w)=cap(v,w)-flow(v,w)。 注意：两个条件可能同时都成 立，因此就对应两条边。 注意：反向边 注意：正向边