$网络流基本概念$ 、 $网络流·最大流$

$$ \huge 最小割 $$

割的定义

$把G的点集V分为不重不漏的两部分S,T,其中s\in S, t \in T$

$割的容量C_{(S,T)}=\sum _{u\in S} \sum _{v \in T} C_{(u,v)}$

$割的流量f_{(S,T)} = \sum _{u \in S} \sum _{v\in T} f_{(u,v)} - \sum _{v \in T} \sum _{u\in S} f_{(v,u)}$

最小割

$容量最小的割被称为最小割$

最小割最大流定理

$下列条件只要满足一个,另外两个一定成立$

1. $可行流f是最大流$
2. $可行流的残留网络G_f里不存在增广路$
3. $存在某个割[S,T],|f|=C[S,T],可行流流量等于割的容量$

证明

引理

1. $f[A,A] = 0$
2. $A \cap B = \phi , f[A,V] + f[B,V] = f[A \cup B , V]$
3. $源点s \notin A , f[A,V] = 0 (流量守恒)$

$对于一张图G的任意一个可行流f和任意一个割[S,T]$

$f[S,T] = f[S,V] - f[S,S] = f[S,V] = f[s,V] + f[S - ${$s$}$,V] = f[s,V] = |f|$

$C[S,T] \ge f[S,T] = |f|, 任何割的容量 \ge 任何可行流的流量 , 即最小割 \ge 最大流$

条件1推条件2

$可行流f是最大流$

$=> 可行流的残留网络G_f里不存在增广路$

$假设G_f中存在增广路,P表示这条路径上所有边的残余网络的最小值$

$那么如果给增广路里的每条边流量都加上P,变成f’$

$f’也一定是一个可行流,且|f’| > |f|,即f不是最大流,故假设不成立$

$证毕$

条件2推条件3

$可行流的残留网络G_f里不存在增广路$

$ => 存在某个割[S,T],|f| = C{[S,T]},可行流流量等于割的容量$

$S表示在G_f中从S出发能到达的所有点集合$

$T = V - S$

$x \in S , y \in T , f(x,y) = c(x,y)$

$x \in T , y \in S , f(x,y) = 0$

$|f| = f[S,T] = \sum_{u \in S} \sum_{v \in T} f(u,v) - \sum_{u \in S} \sum_{v \in T} f(v,u) = \sum_{u \in S} \sum_{v \in T} c(u,v) = C[S,T]$

$证毕$

条件3推条件1

$存在某个割[S,T],|f|=C[S,T],可行流流量等于割的容量$

$=> 可行流f是最大流$

$由于最小割 \ge 最大流$

$|f| = C[S,T] \ge 最小割 \ge 最大流, 即|f| \ge 最大流$

$而最大流 \ge |f|$

$所以f是最大流$

$证毕$

补充

定理

$最小割 = 最大流$

证明

$先求出最大流f$

$在最小割最大流定理中,已满足条件1,那么条件3也成立$

$即存在割的容量C[S,T] = 最大流,又因为C[S,T] \leq 最大流, 不能再小了$

$故最小割 = 最大流$

$那么求最小割就是求最大流$