OCR D2 2009 June — Question 1

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2009
SessionJune
TopicPermutations & Arrangements
TypeAssignment/allocation matching problems
1
  1. A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( \(F\) ), his mother Gwen ( \(G\) ), his wife Helen ( \(H\) ), his son Jack ( \(J\) ) and Mr King ( \(K\) ). The table shows who likes which rolls.
    \(F\)\(G\)\(H\)\(J\)\(K\)
    Avocado and bacon\(( A )\)\(\checkmark\)\(\checkmark\)
    Beef and horseradish\(( B )\)\(\checkmark\)\(\checkmark\)\(\checkmark\)\(\checkmark\)
    Chicken and stuffing\(( C )\)\(\checkmark\)\(\checkmark\)
    Duck and plum sauce\(( D )\)\(\checkmark\)\(\checkmark\)
    Egg and tomato\(( E )\)\(\checkmark\)
    1. Draw a bipartite graph to represent this information. Put the fillings ( \(A , B , C , D\) and \(E\) ) on the left-hand side and the members of the family ( \(F , G , H , J\) and \(K\) ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
    2. Draw a second bipartite graph to show this incomplete matching.
    3. Construct the shortest possible alternating path from \(E\) to \(K\) and hence find a complete matching. State which roll each family member has with this complete matching.
    4. Find a different complete matching.
  2. Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{Family member}
    \(F\)\(G\)\(H\)\(J\)\(K\)
    Lemon\(L\)88881
    Mandarin\(M\)48642
    Nectarine\(N\)99971
    Orange\(O\)46543
    Peach\(P\)69750
    \end{table} The smaller entries in each column correspond to fruits that the family members liked most.
    Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
    Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?
This paper (4 questions)
View full paper
Q1 Q2 Q3 Q4