Lesson 5: Allocation problems and bipartite graphs

Finding an allocation from a bipartite graph

SkillBipartite graphs and allocation tables

Worked example

  • Foundation

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?

1 of 4 steps
  1. Step 1: Start with the forced choices

    Lena has only one edge, so Lena – Canteen. Noah has only one edge, so Noah – Gate.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Allocate any person (or task) with only one possible partner.

  2. Cross off what is taken and repeat.

  3. If you ever have a free choice, try each option to find every allocation.

Save your progress with a free account