7.02p Networks: weighted graphs, modelling connections

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

5 The table shows the weights on the arcs of a network.

1. Draw the network.
2. Apply Dijkstra's algorithm to find the least weight route from G to D. (Do this on the network you drew for part (i).) Give your route and its total weight.
3. Find by inspection the route from \(G\) to \(D\) such that the minimum of the weights for arcs on the route is as large as possible. Give your route and its minimum arc weight. Give an application in which this might be needed.
4. Consider how Dijkstra's algorithm could be modified to solve the problem in part (iii). Explain how to update working values. Explain how to select the next vertex to be permanently labelled.

7.

1. Define the terms
   1. cut,
   2. minimum cut, as applied to a directed network flow. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299} The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
2. State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\). Given that one of these two cuts is a minimum cut,
3. find a maximum flow pattern by inspection, and show it on the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
4. Find a second minimum cut for this network. In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
5. State, with a reason, which of these arcs should be added, and the value of the increased flow.

8. \begin{figure}[h] \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-07_521_1402_1170_343}
   \end{figure} Figure 5 shows a feasible flow through the same network.
2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
4. Show the maximal flow on Diagram 2 and state its value.
5. Prove that your flow is maximal.

11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h] \end{figure}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
2. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
   2. Prove that your final flow is maximal.

12. \begin{figure}[h] \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
2. State the maximum flow along
   1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
   2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day.

7. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.

1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
2. Find the values of \(x\) and \(y\), explaining your method briefly.
3. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
4. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
5. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
6. Prove that your flow is maximal.

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T . Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown in Figure 1.

1. Find the capacity of each of the two cuts.
   (2)
2. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   (3)

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   (2)
3. By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.
   (2)
4. Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.
   (3)
5. Prove that the flow is now maximal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated directed network. The number on each arc is its capacity. \begin{figure}[h] \end{figure} Figure 3 shows an initial flow through the same network.

1. State the values of flows \(a , b\) and \(c\), and the value of the initial flow.
2. By entering values along HG, HT and FG, complete the labelling procedure on Diagram 1 in the answer book.
3. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
4. State the value of the maximum flow through the network.
5. Show your maximum flow on Diagram 2 in the answer book.
6. Prove that your flow is maximal.

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

5

1. Capacity = \(\_\_\_\_\)
2. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
4. Maximum flow = \(\_\_\_\_\) Cut: \(\mathrm { X } = \{\) \} \(\quad \mathrm { Y } = \{\)
5. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-6_597_1577_404_283}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the \(\operatorname { arcs } A C\) and \(A D\) cannot both be full to capacity and why the \(\operatorname { arcs } D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

2 The network models a cooling system in a factory. Coolant starts at \(A , B\) and \(C\) and flows through the system. The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow. \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}

1. Add a supersource, \(S\), and a supersink, \(T\), to the copy of the network in your answer book. Connect \(S\) and \(T\) to the network using appropriately weighted arcs.
2. (a) Find the capacity of the cut that separates \(A , B , C\) and \(E\) from \(D , F , G\) and \(H\).
   (b) Find the capacity of the cut that separates \(A , B , C , D , E\) and \(F\) from \(G\) and \(H\).
   (c) What can you deduce from this value about the maximum flow through the system?
3. Find the maximum possible flow through the system and prove that this is the maximum.
4. Describe what effect increasing the capacity of \(C E\) would have on the maximum flow.

5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from \(S\) to \(T\). \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}

1. How many litres per second are currently flowing along the route SACHT?
2. How many litres per second are currently flowing from \(S\) to \(T\) ?
3. What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
4. Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\). The single vertex \(E\) is replaced by the pair of vertices \(E _ { 1 }\) and \(E _ { 2 }\), together with the \(\operatorname { arc } E _ { 1 } E _ { 2 }\).
5. What does the \(\operatorname { arc }\) joining \(E _ { 1 }\) and \(E _ { 2 }\) tell you about the flow at \(E\) ?
6. Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\).

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at \(S\) to a sink at \(T\). Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from \(S\) to \(T\). Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down the capacity of \(\operatorname { arc } F T\) and of \(\operatorname { arc } D T\). Find the value of the cut that separates the vertices \(S , A , B , C , D , E , F\) from the sink at \(T\).
2. (a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along \(S - C - B - F - T\).
   (b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
3. Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

1. This question should be answered on the sheet provided.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.

1. Illustrate this situation as a complete network showing the shortest distances.
   (2 marks)
2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
   (2 marks)
3. Interpret the tour found in part (b) in terms of the original network.
   (2 marks)

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

5 A garden centre sells mixed packs of flower bulbs.
Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.

1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Six workers, Anthony, Beth, David, Jacob, Kantola and Miri, are to be allocated to six tasks, 1, 2, \(3,4,5\) and 6 . Figure 3 shows the possible allocations of the workers, and an initial matching is shown in Figure 4.

1. Write down the technical name given to the type of diagram shown in Figure 3.
2. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and your improved matching. Anthony now agrees to add task 6 to his possible allocations.
3. Starting with your improved matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.

6. This question is to be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.

1. Explain why it is not possible to achieve a flow of 30 through the network from \(S\) to \(T\).
2. State the maximum flow along
   1. \(S A B T\)
   2. SCET.
3. Show these flows on Diagram 1 of the answer sheet.
4. Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from \(S\) to \(T\). Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
5. Indicate a maximum flow on Diagram 3.
6. Prove that your flow is maximal.

1. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow from S to T .

1. State the value of the feasible flow.
   (1)
2. Find the capacity of cut \(\mathrm { C } _ { 1 }\) and the capacity of cut \(\mathrm { C } _ { 2 }\) (2)
3. By inspection, find a flow-augmenting route to increase the flow by two units. You must state your route.
   (1)
4. Prove that, once the flow-augmenting route found in (c) has been applied, the flow is now maximal.
   (3)

1. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The numbers in circles represent an initial flow from S to T . The other number on each arc represents the capacity, in litres per second, of the corresponding pipe.

1. 1. State the value of \(x\)
   2. State the value of \(y\)
2. State the value of the initial flow.
3. State the capacity of cut \(C _ { 1 }\)
4. Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route. The flow-augmenting route from (d) is used to increase the flow from S to T .
5. Prove that the flow is now maximal. A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
6. 1. Complete Diagram 1 in the answer book to show this restriction.
   2. State the value of the maximum flow through the network with this restriction.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc \(( x , y )\) represents the lower \(( x )\) capacity and upper \(( y )\) capacity of that arc.

1. Calculate the value of the cut \(C _ { 1 }\) and cut \(C _ { 2 }\)
2. Explain why the flow through the network must be at least 12 and at most 16
3. Explain why arcs DG, AG, EG and FG must all be at their lower capacities.
4. Determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure.
5. 1. State the value of the maximum flow through the network.
   2. Explain why the value of the maximum flow is equal to the value of the minimum flow through the network. Node E becomes blocked and no flow can pass through it. To maintain the maximum flow through the network the upper capacity of exactly one arc is increased.
6. Explain how it is possible to maintain the maximum flow found in (d).