Bipartite Graphs & Matching
In short: a bipartite graph splits into two sides with links only crossing between them, and a matching pairs them up with no driver or job reused twice. An augmenting path runs from a free driver to a free job, alternating unused and used links; flipping every link on it grows the matching by exactly one. Kuhn's algorithm is a DFS that looks for such a path from each driver in turn, bumping whoever currently holds a wanted job one level deeper, and a matching is maximum exactly when no augmenting path is left to find.
Every morning at six, Meridian's dispatch board fills up with jobs: van runs, a truck delivery, a bike courier loop, a crane lift at the harbour. Every driver is licensed for some of them. Each driver can take at most one job, and each job needs one driver. The shift lead wants as many jobs covered as possible, and wants it before the first van leaves.
The obvious method is first come, first served. Walk down the drivers and give each one any free job they're licensed for. It's fast, and it's often wrong.
Two sides, links only across
Drivers on the left, jobs on the right, and a link wherever a driver holds the licence. No link ever joins two drivers or two jobs. A graph whose nodes split into two sides like this, with every link crossing between them, is bipartite. A set of links that share no endpoint (no driver twice, no job twice) is a matching, and the shift lead wants a maximum matching.
Not every graph can be split into two sides. BFS can test it by colouring each newly found node the opposite colour to the node that found it. A link between two nodes of the same colour means there's no split:
from collections import deque
near = {"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]}
side = {"a": 0}
queue = deque(["a"])
ok = True
while queue:
n = queue.popleft()
for m in near[n]:
if m not in side:
side[m] = 1 - side[n]
queue.append(m)
elif side[m] == side[n]:
ok = False
print(ok)A graph is bipartite exactly when it has no ring of odd length. Driver-and-job graphs are bipartite by construction, so the question here is the matching.
Why first come, first served fails
can_do = {"ana": ["van", "truck"], "ben": ["truck", "bike"], "cy": ["bike", "crane"], "dee": ["van"]}
taken = set()
covered = 0
for driver in ["ana", "ben", "cy", "dee"]:
for job in can_do[driver]:
if job not in taken:
taken.add(job)
covered += 1
break
print(covered)To get from 3 to 4, three drivers have to move at once: dee takes the van, which pushes ana to the truck, which pushes ben to the bike, which pushes cy to the crane, which nobody had. That chain has a name.
Augmenting paths
An augmenting path starts at an unmatched driver and ends at an unmatched job, and alternates: an unused link, then a used one, then an unused one, and so on. Flip every link on it, so unused become used and used become unused. Every driver and job in the middle swaps one partner for another, and the two ends gain one. The matching grows by exactly one. That flip is the whole algorithm:
An augmenting path alternates unused and used links from a free driver to a free job. Flipping it adds exactly one pair.
First come, first served gives ana the van, ben the truck and cy the bike. 8 nodes, 7 edges, undirected. ana: van, ben: truck, cy: bike.
Berge's theorem closes the argument: a matching is maximum exactly when no augmenting path exists. So the algorithm is to try to find an augmenting path from each driver, and flip it when found.
Kuhn's algorithm
Finding the path is a depth-first search that alternates sides. To place driver d,
try each job they can do: if it's free, take it. If it's held, try to place the
holder somewhere else, which is the same question one level deeper. A tried set
stops the search from going round in circles:
The flip is easy to miss in the code. Every holder[job] = driver along the
successful chain runs as the recursion unwinds, and that reassigns each job to
the new driver. Each driver's search visits each job at most once, so the whole
algorithm is O(V × E). The recursion goes as deep as the longest chain, at
most one level per driver, which is fine for a shift roster. For tens of thousands
of drivers, use the iterative form, or the Hopcroft–Karp algorithm, which finds
many shortest augmenting paths per round in O(E √V).
Space is O(V + E): can_do holds every licence once, holder holds at most one
entry per job, and tried plus the recursion stack hold at most one entry per driver.
The tried set belongs to one attempt
This version creates the set once and shares it between every driver:
Ana can take the truck, which frees the van for ben, so 2 jobs can be covered. This prints 1. Fix it so every driver gets a clean search.
Step through two-colouring on a four-node ring. An even ring splits cleanly:
Your turn to drive it
This is Kuhn's algorithm on the morning roster, drawing each chain it tries and
badging every driver with their current job. Change the order in can_do, or
take away a licence, and watch which chain it finds, or fails to find:
Your Kuhn's algorithm. Each attempt walks an alternating chain, and success flips it, so the matching only ever grows.
When can everyone be placed?
Sometimes the answer is "not everyone", and it helps to know why. Hall's condition: every driver can be placed exactly when every group of drivers is licensed, between them, for at least as many different jobs as there are drivers in the group. Three drivers who can only ever drive the van and the truck can't all work, and when Kuhn's search from the third one fails, the drivers and jobs it tried form exactly such a group.
How much does the search save? The brute-force alternative, checking every subset of the possible driver–job pairs, grows as 2^E. If each driver holds about 3 licences, there are 3n pairs and 2^(3n) subsets, while Kuhn's does about n × 3n steps:
| drivers n | brute force (2^(3n)) | Kuhn's (3n²) |
|---|---|---|
| 5 | 32,768 | 75 |
| 9 | 134,217,728 | 243 |
| 10 | 1,073,741,824 | 300 |
Ten drivers already pass a billion subsets. Brute force is hopeless for even a small depot's roster, while augmenting paths handle thousands of drivers.
❓ Cross-question: "What if some jobs pay more?" Then you want the assignment with the best total, not just the most pairs. That's the assignment problem, solved by the Hungarian algorithm or by min-cost flow. The augmenting-path idea is the same, but each augmentation follows the cheapest alternating chain, found by a shortest-path search.
Idioms & real-world patterns
Matching hides in grid puzzles
Anything that pairs up neighbours on a grid is often a bipartite matching in disguise. Colour the grid like a chessboard, and two squares side by side always have different colours. Pairing adjacent squares (tiles, parking bays, dominoes) is then a matching between black and white squares. The boss exercise parks vans this way.
Cover equals matching, but only on two sides
The capstone asks for the fewest depots that touch every link, a vertex cover. On a general graph that's one of the classic hard problems. On a bipartite graph, König's theorem says it equals the maximum matching size, so it's easy. The same question can be easy or hard depending on the graph's shape, which is why checking for two sides first is worth doing.
⚡ Advanced: matching is a flow
Add a source linked to every driver and a sink linked from every job, give every link capacity 1, and a maximum matching is a maximum flow. Flow algorithms generalise this lesson to capacities, costs and bottlenecks: how much a whole network can carry, and where it chokes. A later Meridian section builds exactly that generalisation — maximum flow, min cut, and paying drivers by the job.
Quick practice
from collections import deque
near = {"a": ["b", "e"], "b": ["a", "c"], "c": ["b", "d"], "d": ["c", "e"], "e": ["d", "a"]}
side = {"a": 0}
queue = deque(["a"])
ok = True
while queue:
n = queue.popleft()
for m in near[n]:
if m not in side:
side[m] = 1 - side[n]
queue.append(m)
elif side[m] == side[n]:
ok = False
print(ok)A triangle is an odd ring and can't be split into two sides, but this prints True for it. The code colours every new node, but never checks an old one. Fix it.
🎯 Your turn
Write assign_drivers(can_do). can_do maps each driver to the jobs they're
licensed for. Each driver does at most one job and each job needs at most one
driver. Return the largest number of jobs covered at once:
assign_drivers({"ana": ["van", "truck"], "ben": ["van"]})→2assign_drivers({"ana": [], "ben": []})→0
Hint: try to place each driver with a fresh tried set, and when a job is taken,
recursively try to place its holder somewhere else.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian is built. ✅