D1: Matchings
Sir Fergus Alecson has a problem. He has five players left to pick for the FA Vase Final but they're being awkward. Brian Bibbs will only play right wing or centre forward; Bruce Stevens will only play on the left wing; Rob Bryanson will only play centre back, centre forward or left wing; Keen Roy can only play midfield or centre forward and Neville Phillips will only play left wing.
Can you help him out by matching each player to a position?
This area of mathematics is called Matchings. Usually the problems that you will be required to solve are straightforward but it's the algorithm that's important.
Not surprisingly, we'll start by drawing a graph of this information.
The type of graph is called a bipartite (two parts) graph. We line the players on the left and the poitions on the right like this...
A bipartite graph is a special graph for when we have two different sets of things (here football players and football positions)
Notice that it makes sense to join a player to a position but it doesn't make any sense to join "midfield" to "centre forward".
This graph shows each possible pairing - we shall use the graph to form an algorithm to solve the problem.
Remember that while a simple problem involving only 5 people and 5 jobs might be quickly solved by a human being, a more complex task such as a school timetable for teachers will be many times more complicated.
We will need a fool-proof algorithm.
Fergus starts by playing Bibbs on the right wing, Bryanson the left and Roy as centre forward.
Unfortunately he is stuck. Let's try to help.