网络流——概念篇 网络 网络表示一个有向图（可能有环），G = (V, E) 每条边 (u, v) ∈ E都有一个权值c(u, v)，称之为容量，对于$(u,v)E ，均有c(u,v)=0$ 其中有两个点： s ∈ V 源点（没有入度） t ∈ V 汇点（没有出度） 流 设 f(u, v)定义在二元组 (u ∈ V, v ∈ V)上的实数函数且满足 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，f(u, v) ≤ c(u, v) 斜对称性：每条边的流量与其相反边的流量之和为 0，即 f(u, v) = − f(v, u) 流守恒性：从源点流出的流量等于汇点流入的流量，即 $xV-{s,t}, {{(u,x)E}}f(u,x)={{x,vE}}f(x,v) $ 那么 f 称为网络 G 的流函数。对于 (u, v) ∈ E，f(u, v)称为边的流量，c(u, v) − f(u, v)称为边的剩余容量。整个网络的流量为 ，∑(s, v) ∈ Ef(s, v)即 从源点发出的所有流量之和。 一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述三个性质。 注：流 ...
