Lectures 8,9

Network Flows

When I do these lectures live, it normally takes me 3 lectures to go through the material slowly and do lots of examples. This is a list of topics that are needed to under network flows. You goal should be to understand each topic.

  • Definition of flow network.
  • The minimum-cut problem.
  • The maximum flow problem.
  • The definition of a residual network.
  • An Augmented path.
  • The statement of the Min-cut, max-flow theorem.
  • The Ford–Fulkerson algorithm.
  • How to use the max-flow algorithm for maximum bipartite matching.

Lecture 8

Lecture 9

  • Alternative mathematical API. Flows that are Skew Symmetric flows, that is $f(u,v)= - f(v,u)$. We’ll do this on the blackboard, but skew symmetric flows are a bit counter intuitive, but they make the proofs and implementation easier. Take a look at the presentation at Wikipedia. This is not examined, and I won’t go into much detail.

  • Min-Cut Max-Flow duality slides 25-36 of NetworkFlow I

  • Bipartite matching slides 1-17 of NetworkFlow II.

Reading Guide

  • Chapter 26, except 26.4 and 26.5 of CLRS3 or Chapter 24 of CLRS4.

What should I know by the end of this set of lectures?

  • Do I understand the definitions of a flow network, min-cuts and maximum flows?
  • Why does the naive greedy algorithm for maximum flow fail?
  • The relation between augmented paths and residual networks.
  • What is the relationship between flows and cuts?
  • What is the relationship between negative flows and residual networks?
  • What does the min-cut max-flow algorithm tell us and how does it help us to derive an algorithm?
  • What is bipartite matching? What are its applications?