Last lesson of the module, and we close with the most human problem of all: pairing things up. Every morning Rutalia must assign couriers to shifts and orders, and not everyone can do everything: whoever rides a bicycle doesn't cover the Industrial Park, whoever lacks a motorcycle license doesn't take the Center's express shift. In 03-05 we left the clue: assignment is a flow with capacities of 1. Here we develop it with its own theory — bipartite graphs, alternating and augmenting paths — implement the classic maximum matching algorithm, present the Hungarian algorithm for the weighted version, and close the circle with the optimal assignment we used to solve with linear programming in 02-01. When we finish, we will review the module's complete graph arsenal.

1. Bipartite graphs and the bipartiteness test with BFS
2. Matchings: definitions and the failure of greed
3. Maximum matching via flow: the explicit reduction
4. Alternating and augmenting paths: the direct algorithm
5. Weighted matching: the Hungarian algorithm and scipy
6. The module 3 graph arsenal, in one table

A graph is bipartite if its vertices can be split into two groups L and R such that every edge crosses from one group to the other (no internal edges). The couriers–shifts graph is bipartite by construction: edges only join people to compatible shifts, never person to person.

Key characterization: a graph is bipartite if and only if it contains no odd-length cycles. And the test is a BFS from 03-02 with one tiny extra — paint alternating levels and watch for contradictions:

Two illustrative tests:

• Rutalia's canonical network (03-01) is not bipartite: it contains the triangle ALM–MER–CEN (a cycle of length 3, odd). The test catches it the moment the BFS tries to paint the triangle's third vertex.
• The compatibility graph of this lesson is, with L = couriers and R = shifts. In general, the test is useful when the bipartition is not given (can I split these zones into "even/odd" for alternate-day delivery without two neighboring zones coinciding? — same question, same BFS).

A matching M is a subset of edges sharing no vertices: nobody appears in two pairs. Vocabulary:

• A vertex is free if no edge of M touches it.
• M is maximum if no matching has more edges. Beware the false friend maximal: "not extendable by adding loose edges", which can be much worse.
• M is perfect if it leaves no vertex free.

The lesson's central instance — 4 couriers, 4 shifts, compatibilities by vehicle and zone (fictional data):

Try the greedy approach (assign each one, in order, the first free shift): Ana→North, Bruno→River, Carla→South… and Dani is left without a shift, because his only option (North) is taken. Three pairs and a maximal but not maximum matching: a perfect one exists. Greed fails again (02-02 vaccinated us), but this time the repair does not demand exponential backtracking: there is structure to exploit.

First solution: cash in the advance from 03-05. The reduction turns the matching into a flow:

• Source s → each courier with capacity 1.
• Courier → compatible shift, capacity 1, directed towards the shift.
• Each shift → sink t, capacity 1.

Three weighty observations:

• The capacities of 1 encode "each person one shift, each shift one person"; the integrality of Ford-Fulkerson (03-05) guarantees whole pairs, not half-assignments.
• The maximum flow (4) is the size of the maximum matching: a perfect assignment exists, greed simply wasn't finding it.
• With Edmonds-Karp on this network the cost comes to O(n·m) for bipartite graphs with unit capacities (each augmentation adds 1 and there are at most n augmentations). A faster specialized algorithm exists (Hopcroft-Karp, O(m·√n)); same principle, batched augmentations.

The reduction works, but it is worth seeing the machinery without the flow disguise, because it has a name of its own and elegant theory. Given a matching M:

• An alternating path alternates edges outside M and inside M.
• An augmenting path is an alternating path that starts and ends at free vertices.

If an augmenting path exists, M can be improved: flip its edges (those outside come in, those inside go out) and the matching gains exactly one pair. In our example, with greed stuck at 3, the augmenting path is:

Dani (free) — North (edge outside M) — Ana (North's current partner) — Center (outside M, and Center is free).

Flip: Dani–North comes in, Ana–North goes out, Ana–Center comes in. Result: 4 pairs. Berge's theorem closes the theory: M is maximum if and only if no augmenting path exists. It is the exact analogue of "no augmenting path in the residual" from 03-05 — in fact, a matching augmenting path is a flow augmenting path viewed without the source and the sink.

The classic algorithm (Kuhn's algorithm) looks for an augmenting path from each free courier with a DFS that recursively "evicts":

How to read the DFS, which is the heart of the algorithm:

• try_assign(r, ...) asks: can r end up matched? It scans r's compatible shifts; if one is free, done. If it is taken, it asks recursively whether the occupant can move — that is, literally, walking an alternating path.
• blocked prevents cycles within a single attempt (each shift is considered once per search), guaranteeing O(m) per courier: O(n·m) total.
• The cascade of reassignments on returning True is the "flipping of the augmenting path" made code: each level of the recursion rewrites one pair.
• The concrete outcome (who ends up with what) can vary with the exploration order; the matching's size never does — Berge guarantees it.

It is important to fence off the territory: everything above is for bipartite graphs. In general graphs (pairing couriers with each other for tandem routes, for example) odd cycles complicate alternating paths and Edmonds' Blossom algorithm is needed — it exists, it is polynomial, and it is beyond this course's scope.

So far, binary compatibility: can or cannot. Rutalia's reality is finer: everyone can do almost everything, but at different costs (minutes from each courier's base to the shift's zone). The problem becomes the assignment problem: minimum-cost perfect matching.

The Hungarian algorithm solves it in O(n³). At a conceptual level (enough for this course):

1. Subtract from each row its minimum and from each column its own: the costs become ≥ 0 with at least one 0 per row and column. Subtracting a constant from a row does not change which assignment is optimal (every assignment uses exactly one cell of that row) — only the value changes.
2. Look for a perfect matching using only 0-cells: that is exactly an unweighted maximum bipartite matching — the previous section's algorithm!
3. If none exists, a potential adjustment creates new, "well-oriented" zeros and the process repeats. The theory justifying it is linear programming duality — the same foundation as the simplex we brushed against in 02-01: assignment is an LP whose optimum always lands on integers.

In professional practice you don't implement it by hand; scipy ships it ready (it is the same optimal assignment we posed as an LP in 02-01, now with a specialized algorithm):

Optimum: Ana→Center (3), Bruno→River (2), Carla→South (2), Dani→North (3) = 10 minutes of total travel. In this instance every courier gets their individually cheapest shift — a stroke of luck that doesn't always happen: with costs [[1, 2], [1, 5]] both want the first column, and the global optimum (2 + 1 = 3) forces the first one to yield. That tension between individual and global optimum is precisely what the Hungarian algorithm arbitrates, and what the greedy "everyone to their minimum" cannot resolve.

To maximize compatibility instead of minimizing cost, just use linear_sum_assignment(matrix, maximize=True) (or negate the matrix): same algorithm.

Module closed. This is the full arsenal, with the business question each piece answers:

And the course's debts, settled: the heap of 01-04 powered Dijkstra and Prim; the union-find of 01-04 held up Kruskal; the DP of 01-03 reappeared in Floyd-Warshall; the BFS of 03-02 beats inside Edmonds-Karp and the bipartiteness test; and the travel-time matrix of 03-03 is what fed module 2's TSP.

• Confusing maximal with maximum: the Ana/Bruno/Carla greedy produces a maximal matching (not extendable with one loose edge) that leaves Dani at home. Maximum demands augmenting paths; don't trust "I can't add anything more".
• Applying Kuhn's algorithm to a non-bipartite graph: odd cycles break the alternating-path argument and the result can be silently suboptimal. Run is_bipartite first; if it fails, the problem is one of general matching (Blossom) or of modeling.
• Forgetting the per-attempt blocked set (or sharing it across attempts): without it, the DFS can loop; shared across couriers, it forbids legitimate reassignments and shrinks the result.
• Solving weighted assignment by trying permutations: n! all over again (02-02). At n = 15 it is already unworkable; the Hungarian does it in O(n³), exactly. Save brute force for verifying tiny instances.
• Non-square cost matrix in linear_sum_assignment: scipy accepts it (it assigns only min(rows, columns) pairs), but it interprets the surplus as spare resources; if you need "uncovered shift = penalty", add dummy columns with that explicit cost. Model it — don't let the tool decide for you.
• Tip: faced with any "who with whom" problem (people-tasks, vans-routes, orders-slots), draw the bipartite graph before coding. Half the time the solution is a direct reduction to what you already have from 03-05 or from this lesson.

1. Alternate-day delivery. Rutalia wants to split the canonical graph's 9 zones into two groups (Monday/Wednesday/Friday delivery versus Tuesday/Thursday/Saturday) so that no street joins two zones in the same group. Use is_bipartite to show it is impossible, and identify by hand an odd cycle certifying it. Would removing one edge be enough to make it possible?
2. The last-minute absence. In the central instance, Carla calls in sick and Elia arrives, who can only cover Center: compatibilities Ana:{North, Center}, Bruno:{North, River}, Dani:{North}, Elia:{Center}. Does a perfect assignment exist? Run augmenting_matching, and explain the result by finding by hand the set of couriers whose possible shifts "don't stretch far enough" (hint: Hall's theorem — a perfect matching requires every group of k couriers to have at least k possible shifts between them).
3. Assignment with incompatibilities and costs. Combine the lesson's two halves: on the cost matrix of section 5, impose that Dani cannot cover South or Center (wrong vehicle). Represent the prohibition with a very large cost (e.g. 999) and solve with linear_sum_assignment. Does the optimal assignment change compared to the unrestricted version?

Exercise 1:

Certificate by hand: the triangle ALM–MER–CEN is a cycle of length 3. With two groups, two of those three vertices would fall together and the street between them would break the rule. Removing one edge of that triangle is not enough in general: there are more odd cycles (for instance ALM–RIO–CEN–ALM? — ALM–RIO, RIO–CEN, CEN–ALM: another triangle). You would need to break all odd cycles, and here they share edges: removing CEN–ALM eliminates those two triangles, but the 5-cycle ALM–MER–CEN–HOS–?… remains; the honest check is rerunning is_bipartite after each removal. Moral: bipartiteness is a global property, not a local one.

Exercise 2:

No perfect assignment: maximum 3. The Hall certificate: the group {Ana, Dani, Elia} collectively reaches only the shifts {North, Center} — 3 people, 2 possible shifts: someone stays out, no matter how the algorithm chooses. Note the duality, familiar by now: when the matching cannot grow, a structural "bottleneck" exists that certifies it (here Hall's deficient set; in 03-05 it was the minimum cut). Good algorithms don't just fail: they explain why.

Exercise 3:

The assignment does not change: the original optimum (Ana→Center, Bruno→River, Carla→South, Dani→North) already avoided the now-forbidden cells, so it still costs 10. The "cost 999" technique is the standard way to mix hard constraints with soft optimization; always verify that no forbidden cell appears in the final solution (if one does, no feasible assignment existed and the 999 is screaming it at you).

Matching closes the module by tying almost all of its pieces together: the bipartiteness test is a BFS from 03-02 with two colors; maximum matching is a flow from 03-05 with capacities of 1, or directly the augmenting-path algorithm, whose guarantee — Berge's theorem — is a sibling of max-flow min-cut; and the weighted version, solved by the Hungarian algorithm or scipy.optimize.linear_sum_assignment, rediscovers the optimal assignment we formulated as linear programming in 02-01. Rutalia now commands a complete arsenal over its urban network: model it (03-01), traverse it (03-02), find shortest routes (03-03), build minimal infrastructure (03-04), measure its throughput and its bottlenecks (03-05) and assign its people optimally (03-06). We have covered structures; the next step is a different muscle: searching and sorting within data. Rutalia's product catalogs, massive delivery logs and route histories are not graphs but volumes — millions of rows where finding and ordering quickly makes all the difference. In module 4 we start with the sharpest and most treacherous tool of all: binary search and its variants (04-01).