网络流

网络与容许流
定义：一个网络\(N(V,E,C)\)是一个赋权有向简单弱连通图，满足：
1. V中恰有一个负度为0的结点s，称为发点（源）；
2. V中恰有一个正度为0的结点他，称为收点（汇）；
3.每条边\(v_i,v_j)\)的边权\(c_{i,j}\)是一个非负实数，称为该边的容量，\(C=(c_{i,j}\)为网络的容量函数。

定义：如果在网络\(N(V,E,C)\)的边集E上定义一个非负实值函数\(f=(f_{i,j})\)，满足一下条件：
1. 容量限制条件，\(f_{i,j}\le c_{i,j}\)；其中等号成立的边称为饱和边。
2. 平衡条件，对每个中间点v，有\(\sum\limits_{u\in N(v)} f_{u,v} = \sum\limits_{u\in N(v)} f_{v,u}.\)

设F为网络\(N(V,E,C)\)所有容许流组成的集合，称\(f_0=\arg\max w(f)\)为网络\(N(V,E,C)\)的最大流。

割切
定义：设S是网络N的结点子集，如果满足\(s\in S, t\in \bar S\)，则\(S\times \bar S\)的所有有向边组成的集合称为N的一个割切，记为\((S,\bar S)\)。其中所有边的容量之和\[C(S,\bar S)=\sum\limits_{(u,v)\in (S,\bar S)} c_{u,v}\]称为割切\((S,\bar S)\)的容量。最小容量的割切称为最小割切。

引理1. 设f是网络N的任一容许流，\((S,\bar S)\)是N的任一割切，则有\[w(f) = \sum\limits_{u\in S,v\in\bar S} f_{u,v} - \sum\limits_{u\in \bar S,v\in S} f_{u,v}\]
定理2. 设f是网络N的任一容许流，\((S,\bar S)\)是N的任一割切，则有\[w(f)\le C(S,\bar S)\]

定理3. 若f是N最大流，则f的流量等于N的最小割切的容量。

    所属分类：离散数学     发表于2022-08-25