图论—最大流及最小费用流

关系： 0?流量?容量图中数据为容量

2 2 2 1 1 流 2 2 容量(c) 流量(f) 最大流量 2 1 2 2 怎么求最大流

求最大流：

v1 (4) (5)

v4 v5 (3) v2 vs (3) vt

v3

(2)

v6

可行流

?

网络N=(V,X,Y,A,C)的一个可行流失指定义在A上的一个整值函数f，使得：

??(1)对?a?A,0?f(a)?c(a),(容量约束);(2)对?V?(X?Y),f(v)?f(v),(流量守恒)其中f(v)表示点v处于入弧上的流量之和，f(v)表示点v处于出弧上的流量和.(5,3) (4,2) (3,2) (3,1) (3,2) y

??可行流存在性

x

(4,2) (3,3) 注：

(1)可行流总是存在的，比如?a?A,f(a)?0，便是任一网络中的一个可行流，这个流称为零值流；（2）对网络中任一可行流f和任一顶点子集S，f(S)表示从中流出的流量，即从S中顶点指向S外的弧上的流量和，f(S)表示流入的流量，即从S外的顶点指向S的弧上的流量之和??流量与最大流

设f是网络N?(V,X,Y,A,C)中的一个可行流，则必有f(X)?f(Y)?Valf称为流f的流量.??N中流量最大的可行流称为的最大流(5,3) (4,2) (3,2) x

(4,2) (3,1) (3,2) (3,3) y