Presentation Assumption
l For entire presentation, we consider
unweighted graphs (all edges have
weight/capacity one)
l All results apply unchanged to arbitrarily
weighted graphs
» Integer weights = parallel edges
» Rational weights scale to integers
» Analysis unaffected
» Some implementation details