You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Pairing up two kinds of thing — workers to jobs, students to projects, applicants to posts — is one of the oldest and most useful questions in discrete mathematics. A matching in a bipartite graph is a set of edges that share no vertex, so each worker gets at most one job and each job at most one worker. Two questions dominate the topic: how large a matching can we make? (the maximum-matching problem, solved by augmenting paths) and what is the cheapest way to assign everyone? (the allocation problem, solved by the Hungarian algorithm). Both have clean, examinable procedures and a satisfying theory — including Hall's marriage theorem, which says exactly when everyone can be matched.
This is the final optimisation topic of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Running the augmenting-path or Hungarian procedure is AO1; constructing and explaining an augmenting path, applying Hall's condition, and interpreting an allocation in context are AO2/AO3. These are high-mark algorithmic questions, so disciplined, fully shown working is essential.
A graph is bipartite if its vertices split into two disjoint sets X and Y with every edge joining an X-vertex to a Y-vertex (none within a set). Workers-and-jobs, students-and-supervisors and applicants-and-posts are all bipartite.
| Term | Definition |
|---|---|
| Matching M | a set of edges, no two sharing a vertex |
| Maximum matching | a matching with the greatest possible number of edges |
| Complete matching | matches every vertex of the smaller set X (so $ |
| Perfect matching | matches every vertex of both sets (needs $ |
A vertex in a matching edge is saturated (matched); otherwise it is unsaturated (free). It is worth distinguishing two words students often conflate. A matching is maximal if you cannot enlarge it by simply adding one more edge to the existing set — a local notion; it is maximum if it has the largest number of edges of any matching — a global notion. A maximal matching can be smaller than the maximum (greedily grabbing the wrong edges can block better pairings), which is exactly why the augmenting-path method, not greedy edge-adding, is needed to guarantee a maximum. A small bipartite graph with workers X={P,Q,R,S} and jobs Y={1,2,3,4}:
graph LR
P((P)) --- j1((1))
P --- j2((2))
Q((Q)) --- j1
Q --- j3((3))
R((R)) --- j2
R --- j4((4))
S((S)) --- j3
The key tool is an alternating path: a path whose edges alternate out of M, in M, out, in, …. An augmenting path is an alternating path that starts and ends at unsaturated vertices (necessarily one in X, one in Y). Because it begins and ends "out of M", it has one more non-matching edge than matching edge; flipping every edge (matched ↔ unmatched) therefore increases the matching size by exactly one.
Procedure.
With the graph of §2 (P:1,2; Q:1,3; R:2,4; S:3) and initial matching M={P−1, Q−3, R−2}, enlarge M.
S is unsaturated. Build an alternating path from S (writing == for an edge in M and − for an edge not in M):
S−3==Q−1==P−2==R−4.
Vertex 4 is unsaturated, so this is an augmenting path. (M1 for a correct alternating path between two unsaturated vertices.) Flipping each edge — the three "−" edges S−3, Q−1, P−2, R−4 enter M; the three "==" edges Q−3, P−1, R−2 leave — gives
M′={S−3, Q−1, P−2, R−4},∣M′∣=4.
All four workers are matched, so M′ is a complete matching. (A1 for the correct enlarged matching after the flip.)
Exam tip. Lay the path out marking which edges are in/out of M; the flip is then mechanical. The path must start and end at unsaturated vertices — a path ending at a saturated vertex is alternating but not augmenting and gives no improvement.
Bipartite graph: A:1,2; B:1; C:2,3. Initial matching M={A−1, C−2}. Enlarge it.
B is unsaturated; its only edge is B−1, and 1 is matched to A. Build:
B−1==A−2==C−3.
Vertex 3 is unsaturated, so augment: B−1, A−2, C−3 enter; A−1, C−2 leave. New matching M′={B−1, A−2, C−3}, size 3 — every vertex of X={A,B,C} is now matched, a complete matching. No unsaturated X-vertex remains, so M′ is maximum.
When does a complete matching of X into Y exist at all? Hall's theorem gives the exact condition. For a subset S⊆X write N(S) for the set of all Y-vertices adjacent to some vertex of S. Then a complete matching of X exists if and only if
∣N(S)∣≥∣S∣for every subset S⊆X.
This is Hall's condition: every group of k workers must, between them, be qualified for at least k jobs. The condition is obviously necessary (if some k workers share only k−1 jobs, they cannot all be placed); the depth of the theorem is that it is also sufficient. To disprove matchability you exhibit one bottleneck set S with ∣N(S)∣<∣S∣.
Workers A,B,C with A:1; B:1; C:1,2. Can all three be matched?
Take S={A,B}. Then N(S)={1}, so ∣N(S)∣=1<2=∣S∣. Hall's condition fails, so no complete matching exists — A and B compete for the single job 1. (B1 for the bottleneck set; B1 for the correct conclusion.)
The allocation (assignment) problem asks for the one-to-one assignment of n workers to n jobs that minimises total cost, given a cost matrix C. Brute force tries all n! assignments — 6 for n=3 but 3,628,800 for n=10 — so we use the Hungarian algorithm, which exploits a key fact: adding (or subtracting) a constant to any whole row or column of C does not change which assignment is optimal (it shifts every assignment's total by that constant, because each row and each column is used exactly once). We use this to create zeros, then seek an assignment lying entirely on zeros — which, costing nothing in the reduced matrix, must be cheapest in the original. The covering-line count is the cleverness: it detects, without trial and error, whether enough independent zeros yet exist.
Procedure.
Minimise the cost of assigning A, B, C to jobs 1, 2, 3:
| Job 1 | Job 2 | Job 3 | |
|---|---|---|---|
| A | 7 | 3 | 5 |
| B | 2 | 4 | 6 |
| C | 5 | 8 | 1 |
Row reduction (row minima 3,2,1):
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 4 | 0 | 2 |
| B | 0 | 2 | 4 |
| C | 4 | 7 | 0 |
(M1 for correct row reduction.) Column reduction: column minima are all 0, so no change. Cover the zeros: the zeros sit at (A,2),(B,1),(C,3) — one in each row and column — so the minimum cover needs 3 lines =n. An optimal assignment exists on the zeros. (A1 for recognising 3 lines =n.)
Assignment: A→2, B→1, C→3, total cost 3+2+1=6. (A1 for the assignment and cost, read from the original matrix.)
Minimise:
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 4 | 2 | 8 |
| B | 4 | 3 | 7 |
| C | 3 | 1 | 6 |
Row reduction (minima 2,3,1) then column reduction (column minima 1,0,4) give
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 1 | 0 | 2 |
| B | 0 | 0 | 0 |
| C | 1 | 0 | 1 |
Cover the zeros: row B and column 2 cover all zeros using just 2 lines <3, so we must augment. The smallest uncovered entry is 1 (e.g. cell (A,1)). Subtract 1 from all uncovered entries, add 1 to the doubly-covered entry (B,2):
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 0 | 0 | 1 |
| B | 0 | 1 | 0 |
| C | 0 | 0 | 0 |
Now an independent set of three zeros exists — e.g. (A,2),(B,3),(C,1) — so the minimum cover is 3=n. Assignment: A→2, B→3, C→1, cost from the original matrix 2+7+3=12. (The optimum 12 is shared by other assignments such as A→1,B→3,C→2; the algorithm returns one optimal solution.)
(Specimen-style — not from any past paper.)
Three machinists W, X, Y are to be assigned to three tasks I, II, III. The time (minutes) each takes is shown. Assign one machinist per task to minimise total time.
| I | II | III | |
|---|---|---|---|
| W | 9 | 11 | 14 |
| X | 6 | 15 | 13 |
| Y | 12 | 13 | 16 |
(a) Reduce the matrix by rows and then columns. [3] (b) Find the optimal assignment and its total time. [3]
Model solution. (a) Row minima 9,6,12:
| I | II | III | |
|---|---|---|---|
| W | 0 | 2 | 5 |
| X | 0 | 9 | 7 |
| Y | 0 | 1 | 4 |
Column minima 0,1,4:
| I | II | III | |
|---|---|---|---|
| W | 0 | 1 | 1 |
| X | 0 | 8 | 3 |
| Y | 0 | 0 | 0 |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.