Maximum flow

Part 3 · Flows · Chapter 5 · Lecture notes, volume 3 (PDF) · Exercises: Maximum flow · App: Maximum flow: Ford–Fulkerson and Edmonds–Karp

• 5.1 The maximum flow problem

  Open

• 5.2 Cuts

  Open

• 5.3 The residual network

  Open

• 5.4 The max-flow min-cut theorem

  Open

• 5.5 The Ford–Fulkerson algorithm

  The number of augmentations

  Open

• 5.6 The Edmonds–Karp algorithm

  Open

• 5.7 Applications

  Maximum matching in a bipartite graph · Arc-disjoint paths

  Open

Prerequisites

• From this module, Chapter 1 «Graphs»: directed paths, the breadth-first search and the depth-first search.

• From this module, Chapter 4 «Network flow models»: flow conservation, the flow across a cut, the minimum cost flow model and its integer vertices.

• From the module Linear Programming, Chapter 15 «The geometry of Linear Programming»: a linear function attains its maximum over a nonempty bounded polyhedron.

Objectives

At the end of this chapter you will be able to:

• state the maximum flow problem and write its LP model;

• compute the capacity of an \(s\)–\(t\) cut, and use cuts as upper bounds on the value of every flow;

• build the residual network of a flow, find an augmenting path and its bottleneck, and augment the flow;

• prove the max-flow min-cut theorem and the integrality theorem;

• run the Ford–Fulkerson and the Edmonds–Karp algorithms, read a minimum cut at the stop, and give their running times;

• compute a maximum matching in a bipartite graph and a maximum set of arc-disjoint paths as maximum flows.

---

Next: 5.1 The maximum flow problem

---

Exercises on this chapter: Maximum flow

In the interactive lab: Maximum flow: Ford–Fulkerson and Edmonds–Karp.