Outline

• Definition of a flow network
  flow network -- a weighted directed graph, with source and sink, capacity constraints of arcs; the flow conservation rule, total flow through the network
• Finding maximum flow
  minimum cut in a network, residual capacity of arcs and augmenting (residual or "unsaturated") paths, simple Ford-Fulkerson's augmentation algorithm, the "max-flow min-cut" theorem, overview of improved algorithms
  
• Generalized network flow problems and applications
  vertex capacities, (min-capacities, multi-commodity flow), applications in bipartite matching, Menger's theorem, systems of distinct representatives
  

Goals

The main goal of this lecture is to teach students about another basic problem of combinatorial optimization -- the network flow problem. Similarly as with the MST problem (Lecture 5), simple, elegant and fast algorithmic solutions of this problem are known. Moreover, the "max-flow min-cut" theorem is stated and proved, and its numerous consequences are given. Among the consequences; an efficient solution of the bipartite matching problem is outlined, a proof of Menger's theorem (Lecture 2) is given, and Hall's theorem about systems of distinct representatives is stated and proved as well.

 

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 in the online resources linked below, and in Chapter 6 of Diestel's textbook for advanced study.