MA010 Graph Theory (an online guide)

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.


[BOOK]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.