D1 June 2008 Q2

EdexcelOld spec8 marksAllocation

Figure 1: bipartite graph joining tour guides A, E, G, R, W to coach trips 1 to 5 — Figure 1

Figure 2: initial matching E-2, R-4, W-5 — Figure 2

Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5. A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.

(a) Use the maximum matching algorithm, starting with vertex G, to increase the number of matchings. State the alternating path you used. (2)

(b) List the improved matching you found in (a). (1)

Weidi agrees to be assigned to coach trip 3, 4 or 5.

(d) Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. (3)

Scheme	Marks
G – 5 = W – 3 change status G = 5 – W = 3	M1 A1
	(2)

Scheme	Marks
A – no match E = 2 G = 5 R = 4 W = 3	A1
	(1)

Mark scheme (c)

Scheme	Marks
e.g. R is the only person who can do 1 and the only person who can do 4	B2, 1, 0
	(2)

Notes

1B1: Correct answer, may be imprecise or muddled (bod gets B1) but all nodes refered to must be correct.

2B1: Good, clear, correct answer.

Mark scheme (d)

Scheme	Marks
A – 2 = E – 3 = W – 4 = R – 1 change status A = 2 – E = 3 – W = 4 – R = 1	M1 A1
A = 2 E = 3 G = 5 R = 1 W = 4	A1
	(3)
	(8 marks)

Notes

1M1: Path from A to 1

1A1: CAO including change status (stated or shown) but don’t penalise twice. Chosen path clear.

1A1: CAO must ft from stated path

Misread (remove last two A or B marks if earned.)
A – 2 = E – 3 c.s. A=2 – E = 3 Matching A = 2, E = 3, R = 4 W = 5
Then
G – 5 = W – 4 = R – 1 c.s. G = 5 – W = 4 – R =1
Matching A = 2, E = 3, G = 5, R = 1, W = 4