D1 June 2005 Q5

EdexcelOld spec8 marksAllocation

Figure 3: bipartite graph joining films A to E with times 1 to 5 — Figure 3

Figure 4: initial matching A to 1, B to 4, C to 3, D to 2 — Figure 4

A film critic, Verity, must see five films A, B, C, D and E over two days.

The films are being shown at five special critics’ preview times:
1 (Monday 4 pm),
2 (Monday 7 pm),
3 (Tuesday 1 pm),
4 (Tuesday 4 pm),
5 (Tuesday 7 pm).

The bipartite graph in Figure 3 shows the times at which each film is showing.

Initially Verity intends to see

Film A on Monday at 4 pm,
Film B on Tuesday at 4 pm,
Film C on Tuesday at 1 pm,
Film D on Monday at 7 pm.

This initial matching is shown in Figure 4.

Using the maximum matching algorithm and the given initial matching,

(a) find two distinct alternating paths and complete the matchings they give. (6)

Verity’s son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.

(b) Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. (2)

Mark scheme (a)

Scheme	Marks
\(E - 4 = B - 2 = D - 1 = A - 3 = C - 5\) change status to give	M1 A1
matching \(A = 3\quad B = 2\quad C = 5\quad D = 1\quad E = 4\)	A1 (3)
\(E - 4 = B - 2 = D - 3 = C - 5\) change status to give	M1 A1
matching \(A = 1\quad B = 2\quad C = 5\quad D = 3\quad E = 4\)	A1 (3)
	(6)

Scheme	Marks
e.g. Reference to \(B + E\) and \(4 + 2\)	B2,1,0
	(2)
	(8 marks)