Assignment/allocation matching problems

4 The Head Teacher of a school is allocating five teachers, Amy ( \(A\) ), Ben ( \(B\) ), Celia ( \(C\) ), Duncan ( \(D\) ), and Erica ( \(E\) ), to the five posts of Head of Year 7, 8, 9, 10 and 11. The five teachers are asked which year(s) they would be willing to take. This information is shown below. Amy is willing to take Year 7 or Year 8 . Ben is willing to take Year 7, Year 8 or Year 10. Celia is willing to take Year 8, Year 9 or Year 11. Duncan will take only Year 9.
Erica will take only Year 11.

1. Show this information on a bipartite graph.
2. Initially the Head Teacher assigns Amy to Year 8, Ben to Year 10, Celia to Year 9 and Erica to Year 11. Demonstrate, by using an alternating path from this initial matching, how each teacher can be matched to a year that they are willing to take.

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{d1e453d6-0abb-4a7e-87c1-28275074dd08-02_1040_620_644_703}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.

2

1. Use a Shell sort to arrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 7 & 8 & 1 & 6 & 3 & 4 & 5 & 2 \end{array}$$
2. Write down the number of comparisons on the first pass.

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 .
The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

2
2
\end{tabular}} & \multirow{3}{*}{\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_699_1486_269_366} \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_508_1272_462_366} }
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline \end{tabular} \end{center}

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.

1. Represent this information in a bipartite graph.
2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.

2 Five different integers are to be sorted into ascending order.

1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
   1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
   2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
3. Use your answers from parts (a) and (b) to write down the value of \(x\).

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
   (3 marks)

1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.

1. Represent this information on a bipartite graph.
2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.

2 A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4 . This arrangement of tiles will be called position 4. \begin{table}[h]

1. Apply the algorithm with the inputs \(B = 2\) and \(N = 5\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached.
2. Explain what happens when the algorithm is applied with the inputs \(B = 2\) and \(N = - 5\).
3. Apply the algorithm with the inputs \(B = 10\) and \(N = 37\). Record the values of \(F , G , H , C\) and \(N\) each time Step 9 is reached. What are the output values when \(B = 10\) and \(N\) is any positive integer?

1 Tom has some packages that he needs to sort into order of decreasing weight. The weights, in kg , given on the packages are as follows. $$\begin{array} { l l l l l l l l l } 3 & 6 & 2 & 6 & 5 & 7 & 1 & 4 & 9 \end{array}$$ Use shuttle sort to put the weights into decreasing order (from largest to smallest). Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass. Write down the total number of passes, the total number of comparisons and the total number of swaps used.

1

1. Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
2. The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
3. Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.

2

1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
2. Explain how you know that none of the graphs from part (i) is Eulerian.

12 JUNE 2006
Afternoon
1 hour 30 minutes

• This insert should be used to answer Question 6.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.

6

1. 
   Key:
   \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels)
   \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from \(A\) to \(J =\) \(\_\_\_\_\)
   Length of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) metres
2. 1. \(\_\_\_\_\)
      Shortest distance \(=\) \(\_\_\_\_\) metres
   2. 
      \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
      Shortest distance = \(\_\_\_\_\) metres

1 Two graphs A and B are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down an example of a cycle on graph A .
2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
3. How many arcs would there be in a spanning tree for graph A ?
4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?

1 The memory requirements, in KB , for eight computer files are given below. $$\begin{array} { l l l l l l l l } 43 & 172 & 536 & 17 & 314 & 462 & 220 & 231 \end{array}$$ The files are to be grouped into folders. No folder is to contain more than 1000 KB , so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders.
2. Use the first-fit decreasing method to group the files into folders. First-fit decreasing is a quadratic order algorithm.
3. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers?
4. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
   A simply connected graph is one that is both simple and connected.
5. (a) Draw a graph with five vertices of orders \(1,1,2,2\) and 4 that is neither simple nor connected.
   (b) Explain why your graph from part (a) is not semi-Eulerian.
   (c) Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.
6. (a) Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour.
   (b) Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.
2. Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.
3. Explain why there is no simply connected graph with exactly four vertices of orders \(1,2,3\) and 4. State which of the properties 'simple' and 'connected' cannot be achieved.
4. A simply connected Eulerian graph has exactly five vertices.
   (a) Explain why there cannot be exactly three vertices of order 4.
   (b) By considering the vertex orders, explain why there are only four such graphs. Draw an example of each.

8 \section*{PLEASE DO NOT WRITE ON THIS PAGE} RECOGNISING ACHIEVEMENT

3 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why it is impossible to draw a graph with exactly five vertices of orders \(1,2,3,4\) and 5.
2. Explain why there is no simply connected graph with exactly five vertices of orders \(2,2,3,4\) and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.
3. Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.
4. Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree. In the graph below the vertices represent buildings and the arcs represent pathways between those buildings.
   \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}
5. By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
   (b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
   (c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Revision classes}

   Student number	C1	C2	C3	C4	M1	M2	S1	S2	D1	D2
   1	✓	✓
   2				✓						✓
   3			✓	✓
   4			✓			✓
   5								✓	✓
   6		✓				✓
   7					✓			✓
   8	✓						✓
   9						✓				✓
   10					✓		✓

   \end{table}
2. (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
   (b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
   (c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$

1. Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
2. Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
3. Find a way to pack the boxes into the van so that she makes as few deliveries as possible.

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest distance (in metres) from \(A\) to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as \(A\). The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
2. Showing your working, find the length of the shortest route that Alex can take, starting and ending at \(A\), to find every clue. The clues tell Alex that the treasure is located at the point marked as \(H\) on the network.
3. Write down the shortest route from \(A\) to \(H\). Zac also starts at \(A\) and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to \(A\). Instead he proceeds directly to the treasure at \(H\).
4. Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

1 The following list is to be sorted into increasing order, from smallest to largest. $$\begin{array} { l l l l l l } 15 & 7 & 9 & 26 & 10 & 4 \end{array}$$ Bubble sort is to be used, starting at the left-hand end of the list, so that after the completion of the first pass the largest value will be at the right-hand end of the list.

1. Write down the list that results at the end of the first pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
2. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 4 & 10 & 15 & 26 \end{array}$$ Write down the list that results at the end of the fourth pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
3. How many comparisons are needed in total to sort the list using bubble sort? Shuttle sort is then used to sort the original list, into increasing order, starting at the left-hand end of the list.
4. Write down the list that results at the end of the first pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
5. After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 15 & 26 & 10 & 4 \end{array}$$ Write down the list that results at the end of the fourth pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
6. How many comparisons and how many swaps are made in the fifth pass? In sorting the original list, both methods use a total of 9 swaps.
7. Which of the two methods is the more efficient at sorting this list? Support your answer with a reason.

2

1. A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8
   G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
2. Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
3. By considering the minimum spanning tree for the reduced network formed when vertex \(A\) and all arcs joined to \(A\) are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.

   	A	\(B\)	C	D	E	\(F\)	G	\(H\)
   A	-	10	-	9	10	-	-	-
   B	10	-	8	5	-	-	-	-
   C	-	8	-	9	-	10	-	-
   D	9	5	9	-	6	7	8	-
   E	10	-	-	6	-	一	9	7
   F	-	-	10	7	-	-	5	-
   G	-	-	-	8	9	5	-	8
   H	-	-	-	-	7	-	8	-

4. Apply the nearest neighbour method, starting at \(A\), to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.