• Flow network: directed graph G = (V, E) with the following features
  • Associated with each edge e is a capacity which is a nonnegative number that we denote ce
  • A single source node s in V
  • A single sink node t in V
  • Nodes other than s and t will be called internal nodes
• No edge enters the source s and no edge leaves the sink t
• At least one edge incident to every node
• All capacities are integers
• Value f(e) represents amount of flow carried by edge e
• A flow f must satisfy the following properties
  • Capacity conditions: for each e in E, we have o⇐f(e)⇐ce
  • Conservation conditions: for each node v other than s and t, we have ∑eintoy f(e)= ∑eoutofy f(e)
  • Given a flow network, find a flow of maximum possible value
  • Maximum flow algorithm that we develop here will be intertwined with a proof that the maximum flow value equals the minimum capacity of any such division, called the minimum cut
  • The algorithm will also compute the minimum cut

• Start with zero flow: f(e) = 0 for all e
• Increase value of f by pushing flow along path from s to t up to the limits imposed by the edge capacities: not optimal, get stuck
• We can instead push forward on edges with leftover capacity and push backward on edges that are already carrying flow, to divert it in a different direction
• Define a residual graph Gf of G with respect to f as follows
  • The node set of Gf is the same as that of G
  • For each edge e = (u, v) of G on which f(e)<ce, there are ce-f(e) leftover units of capacity on which we could try pushing flow forward; so we include the edge e=(u, v) in Gf with a capacity of ce-f(e); we will still call edges included this way forward edges
  • For each edge e = (u, v) of G on which f(e) > 0, there are f(e) units of flow that we can undo if we want to by pushing flow backward; so we include the edge e’=(v, u) in Gf with a capacity of f(e); note that e’ has the same ends as e but its direction is reversed; we will call edges included this way backwards edges

The way in which we push flow from s to t in Gt

   Augment(f, P):
     Let b = bottleneck(P, f)
     For each edge (u, v) in P:
	     If e = (u, v) is a forward edge:
		     Increase f(e) in G by b
	     Else (u, v) is a backward edge and let e = (v, u):
		     Decrease f(e) in G by b
	     Endif
     Endfor
     Return(f)

• F is a flow in G

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 Gf:
	     Let P be a simple s-t path in Gf
	     f’ = augment(f, P)
	     update f to be f’
	     update the residual graph Gf to be Gf’
     Endwhile
     Return f

• At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values [f(e)] and the residual capacities in Gf are integers
• Let f be a flow in G and let P be a simple s-t path in Gf. Then, v(f’) = v(f) + bottleneck(P, f); and since bottleneck(P, f) > 0, we have v(f’) > v(f)
• Suppose that all capacities in the flow network G are integers. Then the Ford-Fulkerson Algorithm terminates in at most C iteration of the while loop
• Suppose, as above, that all capacities in the flow network G are integers. Then the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time.
• Somewhat more efficient version of the algorithm would maintain the linked lists of edges in the residual graph Gf as part of the augment procedure that changes the flow f via augmentation

The readability of this section was an 8 out of 10. It was fairly easy to understand considering the fact that we learned about the problem and algorithm in class before the Wiki was assigned. The authors did a really good job of clearing up the places where I was a little fuzzy in understanding in class.

• Use the notion of a cut to develop a much more general means of placing upper bounds on the maximum-flow value
• S-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B
• Capacity of a cut (A, B), which is denoted as c(A, B), is simply the sume of the capacities of all edges out of A
• Let f be any s-t flow and (A, B) any s-t cut. Then, v(f) = f:out(A) – fin(A).
• By watching the amount of flow f sends across a cut, we can exactly measure the flow value: it is the total amount that leaves A minus the amount that swirls back into A
• Let f be any s-t flow, and (A, B) any s-t cut. Then v(f) = f:in(B)-f:out(B).
• Let f be any s-t flow, and (A, B) any s-t cut. Them, v(f) ⇐ c(A, B)
  • The value of every flow is upper bounded by the capacity of every cut

• f has the maximum value of any flow and that (A*, B*) has the minimum capacity of any s-t cut
• If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is an s-t cut (A*, B*) in G for which v(f) = c(A*, B*). Consequently, f has the maximum value of any flow in G and (A*, B*) has the minimum capacity of any s-t cut in G.
• Ford-Fulkerson algorithm terminates when there is no s-t path in the residual graph
• The flow f returned by the Ford-Fulkerson Algorithm is a maximum flow
• Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(M) time
• There can be many minimum capacity cuts in a graph G
• In every flow network, there is a flow f and a cut (A, B) so that v(f)=c(A, B)
• Max-Flow Min-Cut Theorem: in every flow network, the maximum value of an s-t slow is equal to the minimum capacity of an s-t cut

• If all capacities in the flow network are integers then there is a maximum flow f for which every flow value f(e) is an integer
• Allowing capacities to be rational numbers does not make the situation any more general since we can determine the least common multiple of all capacities and multiply them all by this value to obtain an equivalent problem with integer capacities
• For any real flow f of maximum value, the residual graph has no s-t path; otherwise there would be a way to increase the value of the flow; therefore one could prove in every flow network, there is a flow f and a cut (A, B) so that v(f)=c(A, B) in the case of real-values capacities by simply establishing that for every flow network, there exists a maximum flow

The readability of this section was a 7 out of 10. The hard part of this section was remembering exactly what a cut was, but once I did that, it was easy going from there. The authors did a really good job of using clear language to explain the max-flow min-cut theorem and the relationship between flows and cuts.

• Bipartite graph: an undirected graph whose nodes can be partitioned as V = XUY with the property that every edge e in E has one end in X and the other end in Y
• Matching M in G is a subset of of the edges M (sideways U with line under it) such that each node appears in at most one edge in M

• Use an algorithm for the Maximum-Flow Problem to find a maximum matching
• First, we direct all edges in G from X to Y
• Add a node s in X and a node t in Y
• Give each edge in G’ a capacity of 1
• Compute a maximum s-t flow in this network G
• Value of this maximum is equal to the size of the maximum matching in G

• Capacity and conservation conditions are me and so f is an s-t flow of value k
• Set M’ of edges of the form (x, y) on which the flow value is 1
• M’ contains k edges
• Each node in X is the tail of at most one edge in M’
• Each node in Y is the head of at most one edge in M’
• The size of the maximum matching in G is equal to the value of the maximum flow in G’ and the edges in such a matching in G are the edges in such a matching in G are the edges that carry flow from X to Y in G’
• At least one edge incident to each node in the original problem m >=n/2
• Dominated by the time to compute an integer-valued maximum-flow in G’
• By using O(mC) bound, the Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time
• No sophistication necessary
• Augmenting paths are therefore also called alternating paths in the context of finding a maximum matching
• Effect of augmentation: take the edges used backwards out of the matching and replace them with the edges going forward

• Not all bipartite graphs have perfect matchings
• We can decide if the graph has a perfect matching by checking if the maximum flow in a related graph G’ has value at least n
  • By the max-flow min-cut theorem, there will be an s-t cut of capacity less than n if the maximum-flow value in G has value less than n
  • A cut with capacity less than n provides such a certificate
• If a bipartite graph G = (V, E) with two sides X and Y has a perfect matching, then for all A cuts in X we must have |(upside-down L) (A)| >= |A|
• Hall’s Theorem: Assume that the bipartite graph G = (V, E) has two sides X and Y such that |X|=|Y|. Then the graph G either has a perfect matching of there is a subset A cut in X such that |(upside-down L) (A)| < |A|. A perfect matching or an appropriate subset A can be found in O(mn) time.

The readability of this section on a scale of one to ten was a 8. This is because it was just an explanation of how to apply an algorithm that we already knew how to do.

• Many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a max flow or a min cut in a directed graph
• Suppose there can be a set S of sources generating flow and a set T of sinks that can absorb flow
• Sources have fixed supply values and sinks have fixed demand values
• Will not be seeking to maximize a particular value; want to satisfy all the demand using the available supply
• Given a flow network G= (V, E) with capacities on the edges
• Associated with each node v in V is demand dv
  • dv > 0: demand of dv for flow
  • dv < 0: supply of –dv
  • dv=0; neither a source nor a sink
• circulation with demands {dv} is a function that assigns a nonnegative real number to each edge and satisfies the following two conditions: capacity conditions and command conditions
• feasibility problem: whether there exists a circulation that meets the above conditions
• in order for feasible circulation: total supply must equal the total demand
• if there exists a feasible circulation with demands {dv} then the summation of all dv for the graph is 0
• D = summation of positive dv = summation of negative dv

• Attach a super source s* to each node in S and a super sink t* to each node in T
• Create a graph G’ from G by adding new nodes s* and t* to G
• Each node v with dv>0: we add an edge (v, t*) with capacity dv
• Each node with dv<0: we add an edge (s*, u) with capacity –du
• Carry the remainder of structure G over to G’
• Seeking max s*-t* flow
• Cannot be an s*-t* flow in G’ of calue greater than D sine the sut (A, B) with A = {s*} only has capacity D
• Suppose there is a max s*-t* flow in G’ of value d; every edge out of s* and every edge out of t* must be completely saturated with flow
  • If there is a flow of value D in G’, there is such a flow that takes integer values
• There is a feasible circulation with demands {dv} in G if and only if the max s*-t* flow in G’ has value D. If all capacities and demands in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
• The graph G has a feasible circulation with demands {dv}, if and only if for all cuts (A, B), the summation of all dv for v in B ⇐ c(A, B)
• Our network only has a single kind of flow
• We cannot place restriction on which source will supply the flow to which sink; our algorithms will have to decide that

• Want to force the flow to make use of certain edges; can be enforced by placing lower bounds on edges as well as the usual upper bounds imposed by edge capacities
• Flow network G = (V, E) with a capacity ce and a lower bound le on wach edge e; assume 0⇐le⇐ce for each e
• V has demand dv
• Circulation must satisfy capacity and demand conditions

• Reduce this to the problem of finding a circulation with demands but no lower bounds
• Define an initial circulation f0 simply by f0(e) = l, f0 satisfies all capacity conditions
• Lv = f0:in(v)-f0:out(v) = summation of all le of all e into v + summation of all le of all e out of v
  • If Lv=d, satisfies the demand condition
  • If not, need to superimpose a circulation f1 on top of f0 that will clear the remaining “imbalance” at v
• Graph G’ has the same nodes and edges as G
• Capacity of edge e will be ce-le
• Demand of node will be dv-Lv
• Now claim our general construction produces an equivalent instance with demands but no lower bounds
• There is a feasible circulation in G if and only if there is a feasible circulation in G’. If all demands, capacities, and lower bounds in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued