假设 G(V,E) 是一个有限的有向图,它的每条边(u,v)∈E都有一个非负值实数的容量 c(u,v) .如果(u,v)不属于E,我们假设 c(u,v) = 0 .我们区别两个顶点:一个源点 s 和一个汇点 t.一道网络流是一个对于所有结点 u 和 v 都有以下特性的实数函数f:V×V→R
容量限制 (Capacity Constraints):
f(u,v)≤c(u,v)一条边的流不能超过它的容量.
斜对称 (Skew Symmetry):
f(u,v)=-f(v,u)由 u 到 v 的净流必须是由 v 到 u 的净流的相反(参考例子).(既然要看网络流,这是一定要知道的)
流守恒 (Flow Conservati