NETWORK FLOW

Let G(V,E) be a flow network with source s and sink t, and let f be a flow in G.

Let G_f be the residual network of G induced by f, and let f' be a flow in G_f.

(f ↑ f') = f(u,v) + f'(u,v) - f'(v,u)

Then |f ↑ f'| = |f| + |f'|

See the proof

Let G(V,E) be a flow network with source s and sink t, and let f be a flow in G.

Let p be an augmenting path in G_f.

Let f_p be defined as:

    f_p(u,v) = c_f(p)     if (u,v) is on p Residual capacity, minimum c_f(u,v) of edges on p

    f_p(u,v) = 0 otherwise.

Then the function f ↑ f_p is a flow in G with value |f ↑ f_p| = |f ↑| + |f_p| > |f|

See the proof

Let G(V,E) be a flow network with source s and sink t, and let f be a flow in G.

Let (S,T) be any cut of G. Then the netflow across (S,T) is f(S,T) = |f|

See the proof

Let G(V,E) be a flow network with source s and sink t, and let f be a flow in G.

|f| is bounded from above by any c(S,T)

See the proof