$$网络流基本概念$$

$容量$

$在有向图G=(V,E)中,对于每条边(u,v),都给定它的容量,记为C_{(u,v)}$

$流量$

$对于每条边(u,v),都会赋予一个流量,记为f_{(u,v)},满足 0 \leq f_{(u,v)} \leq C_{(u,v)}$

$可行流$

$给每条边赋予一个流量后满足:$

• $容量限制: 0 \leq f_{(u,v)} \leq C_{(u,v)}$
• $流量守恒 : \forall u \in V , \sum_{(u,v)}^{} f_{(u,v)} = \sum_{(v,u)}^{} f_{(v,u)}(源点s,汇点t除外)$

$对于一个可行流f，|f| 表示 f的流量$

$|f| = \sum_{(s,v)} f_{(s,v)} - \sum_{(u,s)} f_{(u,s)} = \sum_{(u,t)} f_{(u,t)} - \sum_{(t,v)} f_{(t,v)}$

$最大流$

$流量最大的可行流$

$残留网络$

$对于每一个可行流f,都对应了一个残留网络G$

$对于可行流上的每一条边f_{(u,v)}$

• $剩余流量 : G’_{(u,v)} = C_{(u,v)} - f_{(u,v)}$
• $退还流量 ：G’_{(v,u)} = -f_{(u,v)}$

$任何一个可行流f + f对应残留网络G’上的可行流f’ = G上的另一个可行流$

$增广路径$

$在残余网络上从S出发,沿大于0的边走到终点的路径被称为增广路径$

$最大流不存在增广路经$

$割$

$把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)}$