Max-flow notes

I assume that most of you are familiar with the notation used for flows on graph, as well as some of the basic results. However, in case you'd like to brush up on some details, we've just posted some notes off the webpage. (CMU/Pitt only, though parts of the book are available through Google books.)

In particular, please have a quick read over the first two chapters for Monday.

• Lecture 16: gives the notation (flows, residual graphs, augmenting paths), as well as Ford and Fulkerson's proof that max-flow = min-cut using augmenting paths.
  
  
• Lecture 17: gives examples where augmenting paths might take a long time (or converges to a non-optimal flow in graphs with non-integer capacities). Then gives two heuristics of Edmonds and Karp to ensure fast convergence.

If you feel like reading the third chapter too (which gives a max-flow algorithm using blocking flows), go ahead --- but I won't rely on that for Monday.