NETWORK FLOW

wikipedia

Graph: A directed graph G(V,E)

Supply & Target: supply(S) and target(T). We want to send from supply to target, there can be infinite supply avaliable.

Capacity: Each edge has some capacity c(x,y) example capacity

Flow: The actual amount we send is called flow f(x,y). And it cannot exceed capacity. 0 ≤ c(x,y) ≤ f(x,y). example flow value see flow animation reset

Flow Conservation: For each node that is not supply or target, the incoming flow is equal to outgoing flow. sum of v1 sum of v2 sum of v3 sum of v4 reset

Value: The value |f| of a flow f is defined as:

      |f| = ∑_{v in V} f(s,v) - ∑_{v in V} f(v,s)

      That is the total flow out of source - the total flow into source

      It is trivial that we want to minimize the flow going back to source.

Output: Compute flow on each edge such that we have maximum flow coming to target. see final sum for this flow reset