# A level mathematics d2 revision notes

#### Matching and allocation

1) Bipartite Graphs and Matching Augmentation Algorithm

They are the graphs that have a set of right nodes and a set of left nodes. The nodes on one side of the the graph (e.g. left) can't join up to each other. This means that the nodes on the left have arcs going only to the right and the nodes on the right have arcs only going to the left. Google the image of a bipartite graph to reinforce what I've said.

For a bipartite graph, initially you are given a certain matching, where the nodes on the left match up to nodes on the right. Some times this matching can be improved (a better combination can be found). Most of the times you are given a question a bit like this one below:

Alan, Brad, Ciara and Dave have to pick one colour of out Pink, Green, Yellow and Red. Alan would prefer Green or Red. Brad would prefer Yellow or Green. Ciara prefers Pink, Green or Yellow. Dave only wants red. Finally, a teacher decides that Alan gets Red, Brad gets Yellow and Ciara gets Green. This leaves Dave with Pink which he didn't want initially. Can this matching be improved?

In this case, you put the A,B,C and D nodes on the left and the P,G,Y and R nodes on the right and then you draw arcs according to what they initially wanted in a bipartite graph - this shows the possible matchings. Once you've drawn the arcs to what they initially wanted, highlight those arcs that signify what the teacher gave them. In the case above, Dave didn't get Red so leave don't draw a node from D to P. This is known as an incomplete initial matching.

To improve the matching follow the algorithm below -

1) Let all the arcs from the possible matchings go from left to right and all the arcs showing the incomplete matching from right to left. 2) Start from the unmatched node on the left and try to follow the arcs to reach the unmatched node on the right where arcs in the possible matchings go from left to right and arcs in the initial incomplete matching go from right to left. 3) Pick the shortest path following Step 2. This is the alternating path. 4) If there is an arc in the alternating path that was in the initial incomplete matching, pick the other arc in the possible matchings that goes out of that particular node. If there isn't a node going common to the arc in the alternating path covered by the initial incomplete matching, leave it like that. 5) Repeat step 4 for any other nodes that might be like the above.

And you should have a final complete matching.

2) Hungarian Algorithm

This is a MINIMISING problem for ALLOCATION problems. So take away the numbers accordingly. But at the end if you have to find the final cost etc. remember to add the number you took away intially, back again at the end. This only works for square arrays (matrices) so add a dummy row accordingly which is the largest element (number) in the array (matrix).