Course contentsShow
← Computer Science
Lesson 1046 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Bipartite Matching via Max Flow

Model bipartite matching as a max flow problem with source, sink, and unit capacity edges.

Bipartite Matching via Max Flow

What You'll Learn

You'll learn how to transform a bipartite matching problem into a maximum flow problem by cleverly adding a source, sink, and unit-capacity edges.

The Core Idea

A bipartite graph has two sets of vertices where edges only connect vertices from different sets (think: jobs and applicants, or students and projects). A matching assigns edges so no vertex appears twice—like pairing each job to at most one applicant.

Here's the elegant insight: model this as a flow network!

The Construction

  1. Add a source vertex s that connects to every vertex in the left set (e.g., all applicants)
  2. Add a sink vertex t that every vertex in the right set connects to (e.g., all jobs)
  3. Give every edge capacity 1

Now the original bipartite edges go left→right, source edges go s→left, and sink edges go right→t.

Why This Works

When you run max flow on this network:

  • Each unit of flow represents one matching pair
  • The capacity-1 constraint ensures no vertex is matched more than once
  • Flow conservation ensures each vertex gets at most one incoming and one outgoing edge
  • The max flow value equals the size of the maximum matching!

Example Analogy

Imagine a hiring fair: applicants (left) can apply to jobs (right). The "hiring office" (source) sends each applicant in, and each job reports back to "HR" (sink) when filled. With capacity-1 pipes, each person gets exactly one job, and each job gets exactly one person—a perfect matching!

Key Takeaway: By adding a source, sink, and unit-capacity edges to a bipartite graph, maximum matching becomes a maximum flow problem solvable with any max flow algorithm (Edmonds-Karp, Dinic's, etc.).