Network models have capacities along edges (how much they can carry), source nodes (sending traffic), and sink nodes (receiving traffic). Given a flow network, find a flow of maximum possible value.

We can push forward on edges with leftover capacity, and we can push backwards on edges that are already carrying slow.

augment(f, P)

Let b=bottleneck(P, f)
For each edge (u,v) in P
	If e=(u,v) is a forwad edge then
		increase f(e) in G by b
	Else ((u,v) is a backward edge, and let e=(u,v))
		decrease f(e) in G by b
	Endif
Endfor
Return(f)

The Ford-Fulkerson Algorithm:

Max-Flow

Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G(f)
	Let P be a simple s-t path in G(f)
	f’=augment(f,P)
	Update f to be f’
	Update the residual graph G(f) to be G(f’)
Endwhile
Return f

At every intermediate stage of the F-F Algorithm, the flow values {f(e)} and the residual capacities in G(f) are integers. Then the it terminates in at most C iterations of the While loop. run time: O(mC) time

Divide the nodes of the graph into two sets: A (s in A) and B (t in B). Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) = f(A out) - f(A in). Also, v(f) = f(B in) - f(B out). By watching the amount of flow f sends across a cut, we can exactly measure the flow value: the total amount that leaves A minus the amount that ‘swirls back’ into A.

v(f) ⇐ c(A,B) The value of every flow is upper-bounded by the capacity of every cut.

If f is an s-t flow such that there is no s-t path in the residual graph G(f), then there is an s-t cut (A*,B*) in G for which v(f) = c(A*,B*). Consequently, f has the max value of any flow in G, and (A*,B*) has the min capacity of any s-t cut in G.

Given a flow f of max value, we can compute an s-t cut of minimum capacity in O(m) time. The max value of an s-t flow is equal to the min capacity of an s-t cut.

Bipartite graph G = (V,E) is an undirected graph whose node set can be partitioned as V = X U Y, with the property that every edge e in E has one end in X and the other end in Y. The Bipartite Matching Problem finds a matching G of the largest size.

First we direct all edges in G from X to Y. Then add node s, and an adge (s,x) from s to each node in X. Add a node t, and an edge (y,t) from each node in Y to t. Each edge has a capacity of 1. The computed max flow in this network is equal to the size of the maximum matching in G’. The size of the max matching in G is equal to the value of the max flow in G’; and the edges are that which carry flow from X to Y in G’.

The F-F Algorithm can be used to find an optimal solution in O(mn) time.