Outline

• Graph connectivity and cuts
  vertex and edge cuts in relation to graph connectivity, Menger's thm. revisited
• Flow networks
  admissible flows, network cuts, the duality "max-flow min-cut" theorem
• Finding maximum flow
  simple Ford-Fulkerson's augmentation algorithm, consequences
• Further extensions and applications
  vertex capacities, min-capacities, back to Menger's theorem, systems of distinct representatives

Goals

There are two mutually related directions in this lecture -- to approach higher graph connectivity from the perspective of cuts in graphs, and to study another basic problem of combinatorial optimization -- the network max-flow problem. Again, both the algorithmic (practical) and the theoretical aspects of this problem are shown, and prime attention is paid to the "max-flow min-cut" duality theorem.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Unfortunately, the network flow problem is not covered in this textbook. Besides the course lecture, students can read from the resources referred below. For advanced study, read also Section 13.5.

Advanced course book [Graph theory (by Reinhard Diestel)]

Study Sections 6.1 and 6.2 for the theory of flow networks, and return to 3.1-3.3 for higher connectivity.

Interactive tutorials