Lecture 6: Network flows
- 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
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.
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.