Net flow
A net flow network is a mere simplification notation over the standard positive flow network. Given a network with V vertices and E edges, where - f(v,u)
implies a flow from v to u, and - c(v,u)
signifies the capacity of the edge (v,u), a net flow must satisfy three constraints: The skew symmetry constraint:
:
This says that for every edge, a positive flow one direction is equivalent to a negative flow from the opposite direction. The capacity constraint:
:
An edge can't 'propagate' more flow than it's capacity. The conservation constraint, which is derived from the skew symmetry constraint:
:
If for every edge (v,u) there is an negative but equal (u,v) flow, the sum of all these edges will be zero. See max flow on how to solve the most common problem expressed in net flow notation.
|
|
