Find missing flow values

3. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
2. 1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.
      (2 marks)

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

1. The diagram above 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.

1. State the values of \(x\) and \(y\).
2. List the saturated arcs.
3. State the value of the feasible flow.
4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
6. Prove that the new flow is maximal.

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.

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\), and \(z\).
   (3)
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\) and \(z\).
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

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

1. 1. Find the value of \(x\).
   2. Find the value of \(y\).
2. List the saturated arcs. Two cuts, \(C _ { 1 }\) and \(C _ { 2 }\), are shown in Figure 1.
3. Find the capacity of
   1. \(C _ { 1 }\)
   2. \(\mathrm { C } _ { 2 }\)
4. Write down a flow-augmenting route, using the arc CF, that increases the flow by two units. Given that the flow through the network is increased by two units using the route found in (d), (e) prove that this new flow is maximal.

3. \begin{figure}[h] \end{figure} Figure 5 represents a network of corridors in a school. The number on each arc represents the maximum number of students, per minute, that may pass along each corridor at any one time. At 11 am on Friday morning, all students leave the hall (S) after assembly and travel to the cybercafé ( T ). The numbers in circles represent the initial flow of students recorded at 11 am one Friday.

1. State an assumption that has been made about the corridors in order for this situation to be modelled by a directed network.
2. Find the value of x and the value of y , explaining your reasoning. Five new students also attend the assembly in the hall the following Friday. They too need to travel to the cybercafé at 11 am . They wish to travel together so that they do not get lost. You may assume that the initial flow of students through the network is the same as that shown in Figure 5 above.
3. 1. List all the flow augmenting routes from S to T that increase the flow by at least 5
   2. State which route the new students should take, giving a reason for your answer.
4. Use the answer to part (c) to find a maximum flow pattern for this network and draw it on Diagram 1 in the answer book.
5. Prove that the answer to part (d) is optimal. The school is intending to increase the number of students it takes but has been informed it cannot do so until it improves the flow of students at peak times. The school can widen corridors to increase their capacity, but can only afford to widen one corridor in the coming term.
6. State, explaining your reasoning,
   1. which corridor they should widen,
   2. the resulting increase of flow through the network.

1. A sheet is provided for use in answering this question.

\begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
2. 1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.

\includegraphics{figure_4} Figure 4 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 2 in the answer booklet. [2]
2. Find the values of \(x\) and \(y\), explaining your method briefly. [2]
3. Find the value of cuts \(C_1\) and \(C_2\). [3]

Starting with the given feasible flow of 68,

1. use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. [6]
2. Show your maximal flow on Diagram 4 and state its value. [3]
3. Prove that your flow is maximal. [2]

\includegraphics{figure_3} Figure 3 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_4} Figure 4 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. [5]
4. Show your maximal flow pattern on Diagram 2. [2]
5. Prove that your flow is maximal. [2]

\includegraphics{figure_1} Figure 1 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_2} Figure 2 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. Diagram 1 \includegraphics{figure_3} [5]
4. Show your maximal flow pattern on Diagram 2. Diagram 2 \includegraphics{figure_4} [2]
5. Prove that your flow is maximal. [2]

(Total 13 marks)

The diagram below shows a network of pipes. \includegraphics{figure_8} The uncircled numbers on each arc represent the capacity of each pipe in m³ s⁻¹ The circled numbers on each arc represent an initial feasible flow, in m³ s⁻¹, through the network. The initial flow through pipe \(SD\) is \(x\) m³ s⁻¹ The initial flow through pipe \(DC\) is \(y\) m³ s⁻¹ The initial flow through pipe \(CB\) is \(z\) m³ s⁻¹

1. By considering the flows at the source and the sink, explain why \(x = 7\) [3 marks]
2. 1. State the value of \(y\) [1 mark]
   2. State the value of \(z\) [1 mark]
3. Prove that the maximum flow through the network is at most 27 m³ s⁻¹ [2 marks]