Lesson 5 of 7 · 15 min
Allocation problems and bipartite graphs
Represent an allocation problem as a bipartite graph and as a table or matrix, then find the best allocation of a small problem by inspection.
What you will be able to do
- Draw a bipartite graph for an allocation problem and write it as a table or matrix.
- Find every possible allocation when only some people can do some tasks.
- Find the minimum or maximum total for a problem by listing all the allocations.
- Explain why inspection becomes impractical for larger problems.
Four volunteers have put their hands up for the school fete, and four stalls need running. Each volunteer can run exactly one stall, each stall needs exactly one volunteer, and not everyone can do everything. Who should go where?
This is an allocation (or assignment) problem: match each member of one group with exactly one member of another.
Definition
Allocation problems and bipartite graphs
An allocation problem has two groups — such as people and tasks — of the same size. A bipartite graph shows it: the people are one set of vertices, the tasks are the other, and an edge joins a person to each task they could do. Edges never join two people or two tasks.
An allocation (or assignment) picks one edge at each vertex, so every person gets exactly one task and every task exactly one person.
Which stalls each volunteer can run.
Worked example
Finding an allocation from a bipartite graph
The bipartite graph in the lesson shows which fete stalls each volunteer can run: Kai can run the Barbecue or the Gate; Lena only the Canteen; Mia the Barbecue, the Canteen or the Raffle; Noah only the Gate.
Find an allocation in which every volunteer runs exactly one stall and every stall has a volunteer. Is it the only one?
Step 1: Start with the forced choices
Lena has only one edge, so Lena – Canteen. Noah has only one edge, so Noah – Gate.
A vertex of degree 1 in the bipartite graph has no choice, so deal with it first.
Step 2: Remove what is taken
Kai could run the Barbecue or the Gate, but the Gate is taken, so Kai – Barbecue.
Step 3: Finish
Mia's options were the Barbecue, Canteen and Raffle. Only the Raffle is left, so Mia – Raffle.
Step 4: Check it is the only allocation
Every step was forced — no other choice was ever possible — so this is the only complete allocation.
Try it yourself first, then check the working one step at a time.
Answer
Kai – Barbecue, Lena – Canteen, Mia – Raffle, Noah – Gate. It is the only possible allocation, because every choice was forced.
Method
Allocate any person (or task) with only one possible partner.
Cross off what is taken and repeat.
If you ever have a free choice, try each option to find every allocation.
Suppose Noah could run the Raffle as well as the Gate, and nothing else changes. How many complete allocations would there be?
Often every person can do every task, but some pairings are better than others. Then each edge of the bipartite graph carries a weight — a cost, a time, a distance or a score — and the same information fits neatly in a table.
Time in minutes for each technician to do each repair job, as a weighted bipartite graph.
| Technician | Job 1 | Job 2 | Job 3 |
|---|---|---|---|
| Ari | 12 | 6 | 7 |
| Bea | 11 | 13 | 14 |
| Cam | 8 | 8 | 12 |
Worked example
The quickest allocation by listing every possibility
Three technicians, Ari, Bea and Cam, each quote a time in minutes to do three repair jobs.
| Job 1 | Job 2 | Job 3 | |
|---|---|---|---|
| Ari | 12 | 6 | 7 |
| Bea | 11 | 13 | 14 |
| Cam | 8 | 8 | 12 |
Each technician does one job. By inspection, find the allocation that gives the smallest total time.
Step 1: Count the allocations
Ari has 3 choices, then Bea 2, then Cam 1: allocations.
Step 2: List them systematically
Writing each as Ari's job, Bea's job, Cam's job:
- 1, 2, 3:
- 1, 3, 2:
- 2, 1, 3:
- 2, 3, 1:
- 3, 1, 2:
- 3, 2, 1:
Fixing Ari's job first, then Bea's, guarantees no allocation is missed or repeated.
Step 3: Choose the smallest
The smallest total is 26 minutes, and only one allocation gives it.
Try it yourself first, then check the working one step at a time.
Answer
Ari – Job 3, Bea – Job 1, Cam – Job 2, for a minimum total of minutes.
Method
List every allocation systematically ( of them).
Total each one.
Choose the smallest (or largest) total, and check whether more than one allocation gives it.
Watch out for
Giving Ari the quickest job (Job 2, 6 minutes) first. The best allocation gives Ari Job 3, because Bea is so much better at Job 1 than at Jobs 2 and 3.
Suppose the table above showed points the technicians earn for each job instead of minutes, and the manager wanted the largest total. What is the maximum total?
Common mistake
Choosing greedily
Giving each person their cheapest task in turn does not guarantee the best total. Ari's quickest job is Job 2 (6 min); then Bea's quickest remaining job is Job 1 (11 min), leaving Cam with Job 3 (12 min). That totals 29 minutes, but the optimum is 26.
Note
Why inspection runs out of steam
With people and tasks there are allocations: 6 for three people, 24 for four and 120 for five. Listing them all is fine for , slow for and hopeless by hand for . The next lesson gives a method that avoids the list.
How many different complete allocations are there of 4 workers to 4 jobs, one job each?
Summary
An allocation problem matches each member of one group with exactly one member of another.
A bipartite graph shows which pairings are possible; weights show their cost, time or score.
The same weights in a table or matrix: one row per person, one column per task.
For small problems, list every allocation systematically and choose the smallest (or largest) total.
There are allocations, so inspection suits only small problems; greedy choices can miss the optimum.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.