===== Chapter 7: Network Flow =====

==== 7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ====

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


==== 7.2 - Maximum Flows and Minimum Cuts in a Network ====

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.


==== 7.5 - A First Application:  The Bipartite Matching Problem ====

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.


==== 7.7 - Extensions to the Maximum-Flow Problem ====

Circulations with Demands:

Suppose there can be multiple source and sink nodes.  Assuming fixed supply and sink values, we incorporate a demand value with each node, negative if it sends flow and positive if it receives flow.  If there is a feasible circulation with demands d(v), then all for all cuts (A,B) SUM(d(v)) <= c(A,B).