网络流
网络与容许流
定义:一个网络\(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_{