Lesson 3

We show how flows can be used to find a maximum matching in a bipartite graph. Turn the bipartite graph \(G(U \sqcup V, E)\) into a network \(G'\) as follows.

1. Add to the set of vertices a source \(s\) and a sink \(t\).
2. Each edge \(\{u,v\}\), where \(u \in U, v \in V\), is replaced with a directed edge \((u,v)\) of capacity \(1\).
3. Add edges \((s,u)\) for all \(u \in U\) and edges \((v,t)\) for all \(v \in V\) with capacity \(1\).