Lesson 5: Allocation problems and bipartite graphs
Finding an allocation from a bipartite graph
SkillBipartite graphs and allocation tables
Worked example
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.
Answer
Kai – Barbecue, Lena – Canteen, Mia – Raffle, Noah – Gate. It is the only possible allocation, because every choice was forced.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.