Assignment/allocation matching problems

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
2. Write down the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(G\). Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at \(A\).
3. Explain why Sheng-Li will need to repeat some streets.
4. Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at \(A\), to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from \(A\), with Sheng-Li delivering to one side of \(A B\) and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel \(A - B - C - E\). At this point Sheng-Li is called back to \(A\). He travels along \(E - C - A\), delivering leaflets on one side of \(C A\). Nadia completes the leaflet delivery on her own.
5. Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
   [0pt] [4]

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

• Two of the green faces are opposite one another.
• The other green face is opposite the yellow face.
• The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h] \end{figure} Fig. 1

1. Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
2. How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
   \end{figure} Fig. 3
3. Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled \(1,2,3\) or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
   From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled \(1,2,3\) and 4 and four nodes each having order two.
5. Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
7. Using your answer to part (vi), show the two possible colourings of the back of the tower.

1 The graph \(\mathrm { K } _ { 5 }\) has five nodes, \(A , B , C , D\) and \(E\), and there is an arc joining every node to every other node.

1. Draw the graph \(\mathrm { K } _ { 5 }\) and state how you know that it is Eulerian.
2. By listing the arcs involved, give an example of a path in \(\mathrm { K } _ { 5 }\). (Your path must include more than one arc.)
3. By listing the arcs involved, give an example of a cycle in \(\mathrm { K } _ { 5 }\).

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h] \end{figure}

1. Draw a tree to show all of the possibilities for the player's first three moves.
2. Show how a player can win in 3 turns.
3. List all squares which it is possible for a counter to occupy after 3 turns.
4. Show that a game can continue indefinitely.

1 Table 1 shows a precedence table for a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and late event time for each vertex of your network, and list the critical activities.
3. Extra resources become available which enable the durations of three activities to be reduced, each by up to two days. Which three activities should have their durations reduced so as to minimise the completion time of the project? What will be the new minimum project completion time?

3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey. \begin{figure}[h] \end{figure}

1. Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town. Give the start town and the end town.
2. Show that there is only one Hamilton cycle in the graph. Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.
3. A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B . Section B (48 marks)

1 The graph shows routes that are available to an international lorry driver. The solid arcs represent motorways and the broken arcs represent ferry crossings.
\includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-2_668_1131_587_466}

1. Give a route from Milan to Chania involving exactly two ferry crossings. How many such routes are there?
2. Give a route from Milan to Chania involving exactly three ferry crossings. How many such routes are there?
3. Give a route from Milan to Chania using as many ferry crossings as possible, without repeating any arc.
   [0pt]
4. Give a route leaving Piraeus and finishing elsewhere which uses every arc once and only once.[3]

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

5 The tasks involved in turning around an "AirGB" aircraft for its return flight are listed in the table. The table gives the durations of the tasks and their immediate predecessors.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Because of delays on the outbound flight the aircraft has to be turned around within 50 minutes, so as not to lose its air traffic slot for the return journey. There are four tasks on which time can be saved. These, together with associated costs, are listed below.

   Task	A	B	D	E
   New time (mins)	20	20	15	15
   Extra cost	250	50	50	100

3. List the activities which need to be speeded up in order to turn the aircraft around within 50 minutes at minimum extra cost. Give the extra cost and the new set of critical activities.

5 A chairlift for a ski slope has 160 4-person chairs. At any one time half of the chairs are going up and half are coming down empty. An observer watches the loading of the chairs during a moderately busy period, and concludes that the number of occupants per 'up' chair has the following probability distribution.

1. Give a rule for using 1-digit random numbers to simulate the number of occupants of an up chair in a moderately busy period.
2. Use the 10 random digits provided to simulate the number of occupants in 10 up chairs. The observer estimates that, at all times, on average \(20 \%\) of chairlift users are children.
3. Give an efficient rule for using 1-digit random numbers to simulate whether an occupant of an up chair is a child or an adult.
4. Use the random digits provided to simulate how many of the occupants of the 10 up chairs are children, and how many are adults. There are more random digits than you will need.
5. Use your results from part (iv) to estimate how many children and how many adults are on the chairlift (ie on the 80 up chairs) at any instant during a moderately busy period. In a very busy period the number of occupants of an up chair has the following probability distribution.

   number of occupants	0	1	2	3	4
   probability	\(\frac { 1 } { 13 }\)	\(\frac { 1 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 5 } { 13 }\)

6. Give an efficient rule for using 2-digit random numbers to simulate the number of occupants of an up chair in a very busy period.
7. Use the 2-digit random numbers provided to simulate the number of occupants in 5 up chairs. There are more random numbers provided than you will need.
8. Simulate how many of the occupants of the 5 up chairs are children and how many are adults, and thus estimate how many children and how many adults are on the chairlift at any instant during a very busy period.
9. Discuss the relative merits of simulating using a sample of 10 chairs as against simulating using a sample of 5 chairs.

2 Two hikers each have a 25 litre rucksack to pack. The items to be packed have volumes of 14, 6, 11, 9 and 6 litres.

1. Apply the first fit algorithm to the items in the order given and comment on the outcome.
2. Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks.
3. The hikers argue that the first fit decreasing algorithm does not produce a fair allocation of volumes to rucksacks. Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing.

1 Consider the following LP.
Maximise \(x + y\)
subject to \(2 x + y < 44\)
\(2 x + 3 y < 60\)
\(10 x + 11 y < 244\)
Part of a graphical solution is produced below and in your answer book.
Complete this graphical solution in your answer book.
\includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-2_1316_1346_916_356}

3 The graph represents four towns together with (two-way) roads connecting them.
\includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886} A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) are paths.

1. There are six paths from \(\mathrm { T } _ { 1 }\). List them.
2. List the paths from \(\mathrm { T } _ { 4 }\).
3. How many paths are there altogether? For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route. Similarly \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route (but note that \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }\) is different).
4. How many routes are there altogether?

1 The numbers on opposite faces of the die shown (a standard die) add up to 7. The adjacency graph for the die is a graph which has vertices representing faces. In the adjacency graph two vertices are joined with an arc if they share an edge of the die. For example, vertices 2 and 6 are joined by an arc because they share an edge of the die.
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_246_213_488_1608}

1. List the pairs of numbers which are opposite each other.
2. Draw the adjacency graph.
3. Identify and sketch a solid which has the following adjacency graph.
   \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_287_307_1027_879}

6 Joan and Keith have to clear and tidy their garden. The table shows the jobs that have to be completed, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities.
3. Each job is to be done by one person only. Joan and Keith are equally able to do all jobs. Draw a cascade chart indicating how to organise the jobs so that Joan and Keith can complete the project in the least time. Give that least time and explain why the minimum project completion time is shorter.

4 A wall 4 metres long and 3 metres high is to be tiled. Two sizes of tile are available, 10 cm by 10 cm and 30 cm by 30 cm .

1. If \(x\) is the number of boxes of ten small tiles used, and \(y\) is the number of large tiles used, explain why \(10 x + 9 y \geqslant 1200\). There are only 100 of the large tiles available.
   The tiler advises that the area tiled with the small tiles should not exceed the area tiled with the large tiles.
2. Express these two constraints in terms of \(x\) and \(y\). The smaller tiles cost 15 p each and the larger tiles cost \(\pounds 2\) each.
3. Given that the objective is to minimise the cost of tiling the wall, state the objective function. Use the graphical approach to solve the problem.
4. Give two other factors which would have to be taken into account in deciding how many of each tile to purchase.

3 John has a standard die in his pocket (ie a cube with its six faces labelled from 1 to 6).

1. Describe how John can use the die to obtain realisations of the random variable \(X\), defined below.

   \(x\)	1	2	3
   \(\operatorname { Probability } ( X = x )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 6 }\)	\(\frac { 1 } { 3 }\)

2. Describe how John can use the die to obtain realisations of the random variable \(Y\), defined below.

   \(y\)	1	2	3
   \(\operatorname { Probability } ( Y = y )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)

3. John attempts to use the die to obtain a realisation of a uniformly distributed 2-digit random number. He throws the die 20 times. Each time he records one less than the number showing. He then adds together his 20 recorded numbers. Criticise John's methodology.

3 The diagram shows three sets, A, B and C. Each region of the diagram contains at least one element. The diagram shows that B is a subset of \(\mathrm { A } , \mathrm { C }\) is a subset of A , and that B shares at least one element with C .
\includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_410_615_342_726} The two graphs below give information about the three sets \(\mathrm { A } , \mathrm { B }\) and C . The first graph shows the relation 'is a subset of' and the second graph shows the relation 'shares at least one element with'. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw two graphs to represent the sets \(\mathrm { X } , \mathrm { Y }\) and Z shown in the following diagram.
   \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_415_613_1388_731}
2. Draw a diagram to represent the sets \(\mathrm { P } , \mathrm { Q }\) and R for which both of the following graphs apply. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_202_264_1980_621} \captionsetup{labelformat=empty} \caption{'is a subset of'}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_200_260_1982_1155} \captionsetup{labelformat=empty} \caption{'shares at least one element with'}
   \end{figure}

1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths.
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}

1. Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths. Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2] Joanna, the householder, wants to walk along all of the paths.
2. Explain why she cannot do this without repeating at least one path.
3. Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated. Joanna has a new path constructed which links the pool directly to the top steps.
4. Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)

5

1. The following instructions operate on positive integers greater than 4.
   Step 10 Choose any positive integer greater than 4, and call it \(n\).
   Step 15 Write down \(n\).
   Step 20 If \(n\) is even then let \(n = \frac { n } { 2 }\) and write down the result.
   Step 30 If \(n\) is odd then let \(n = 3 n + 1\) and write down the result.
   Step 40 Go to Step 20.
   1. Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
   2. Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
   3. Add an instruction to stop the process when \(n\) becomes 1 .
   4. It is not known if, when modified to stop cycling through \(4,2,1\), the instructions form an algorithm. What would need to be known for it to be an algorithm?
2. Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .

   Item	A	B	C	D	E	F
   Weight \(( \mathrm { kg } )\)	2	1	6	3	3	5

   The first-fit algorithm is as follows.
   \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
   1. Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
   2. Place the items in increasing order of weight, and then apply the first-fit algorithm.
   3. Place the items in decreasing order of weight, and then apply the first-fit algorithm. An optimal solution is one which uses the least number of boxes.
   4. Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
   5. First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?

5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown. Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.

1. Complete the table in your answer book by showing the immediate predecessors for each activity.
2. Draw an activity on arc network for these activities.
3. Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
4. Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The data $$x _ { 1 } = 8 , \quad x _ { 2 } = 2 , \quad x _ { 3 } = 4 , \quad x _ { 4 } = 3 , \quad x _ { 5 } = 5 , \quad x _ { 6 } = 1 , \quad x _ { 7 } = 7 ,$$ is to be used in the algorithm given in Figure 1.

1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output using the given data.
2. Explain what the algorithm achieves for any set of data \(x _ { 1 }\) to \(x _ { n }\).

3. A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$\begin{array} { l l l l l l l } 150 & 104 & 200 & 60 & 184 & 84 & 120 \end{array}$$

1. Perform a quick sort to put the seven lengths in descending order. The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
2. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed.
   (4 marks)
3. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods.
   (1 mark)

4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.

1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
2. Draw this initial matching.
3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
4. Explain why no complete matching is now possible.
   (2 marks)

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.

1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
   1. the order in which you labelled the vertices,
   2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
   (4 marks)