D1 January 2012 Q3
3.
Define the terms
Figure 3 shows the possible allocations of six people, Charles (C), Emily (E), George (G), Harriet (H), Jack (J) and Shen (S), to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.
Emily has task 5 added to her possible allocations and Harriet has task 3 added to her possible allocations.
| Scheme | Marks |
|---|---|
| A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. | B2,1,0 |
| (2) |
Notes
a1B1: 2 sets of vertices
a2B1: arcs must go from one set into the other.
| Scheme | Marks |
|---|---|
| A Matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. | B2,1,0 |
| (2) |
Notes
b1B1: pairing or one to one.
b2B1: element(s) from 1 set with element(s) of the other.
| Scheme | Marks |
|---|---|
| Alternating path: J – 4 = E – 2 = C – 3 | M1 |
| Change status: J = 4 – E = 2 – C = 3 | A1 |
| C = 3, E = 2, G = 1, H = 6, J = 4, (S unmatched) | A1 |
| (3) |
Notes
c1M1: Path from J to 3 - or vice versa
c1A1: CAO including change status (stated or shown), chosen path clear.
c2A1: CAO unambiguous. Must ft from stated path, diagram ok
| Scheme | Marks |
|---|---|
| Alternating path: S – 6 = H – 3 = C – 2 = E – 5 | M1 |
| Change status: S = 6 – H = 3 – C = 2 – E = 5 | A1 |
| C = 2, E = 5, G = 1, H = 3, J = 4, S = 6 | A1 |
| (3) | |
| (10 marks) |
Notes
d1M1: Path from S to 5 (or vice versa)
d1A1: CAO including change status (stated or shown), but only penalise once per question, chosen path clear.
d2A1: CAO unambiguous. Must ft from stated paths, diagram ok. Must have both M’s.