A flow network with supplies is a directed capacitated graph with potentially multiple sources and sinks, which may have incoming and outgoing edges respectively. In particular, each node i ϵ V has an integer supply si; if s(i) > 0, i is a source, while if s(i) < 0, it is a sink. Let S be the set of source nodes and T the set of sink nodes.

A circulation with supplies is a function f : E → R+ that satisfies

(a) capacity constraints: for each e ϵ E, 0 ≤ f(e) ≤ c(e).

(b) supply constraints: For each i ϵ V , fout(i) - fin(i) = s(i).

We are now concerned with a decision problem rather than a maximization: is there a circulation f with supplies that meets both capacity and supply conditions?

i. Derive a necessary condition on the supplies s(i) for a feasible circulation with supplies to exist.

ii. Reduce the problem of finding a feasible circulation with supplies to Max Flow.