A Level Mathematics D2 Revision Notes

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > A Level Mathematics D2 Revision Notes

Game Theory

Networks

Critical Path Analysis

Linear Programming

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).

Follow the algorithm below-

1) Reduce rows and then reduce columns (most of the times the question will which one to reduce first but if they don't say it, reduce the rows first and then the columns) Here take away the lowest value in the row or column away from each element in that row or column. If 0 is the lowest value, leave it like that because taking 0 away from each element is not going to change it. 2) You will get 0s so cover all the 0s with the least number of lines. 3) Add the least uncovered element (number in the array) to the zeros. 4) Take away the least uncovered element (number in the array) from EVERY element in the array. 5) Repeat this till you get enough 0s in each row and column. 6) Pick the 0s in a way that it's the only 0 in it's row or column.

That should be your allocation done.

Transportation Problems

• Basics of Transportation Problems
• Finding an Optimal Solution
• Unbalanced Problems