Lesson 1

A classical application of flows is finding matchings in bipartite graphs. Recall that an undirected graph is called bipartite if its vertices are split into two parts such that each edge connects vertices from different parts. A matching in a bipartite graph is a set of its edges, no two of which share a common endpoint.

In the graph shown below, the maximum matching size is two.