Flows in networks

Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow.

The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.

Calculate the capacity of

cut C₁

cut C₂

Using only the capacities of cuts C₁ and C₂, state what can be deduced about the maximum flow through the system.

A scientist monitors the system of pipes in which a fluid now flows from the source, S, to the sink, T.

The scientist initialises the labelling procedure for this system. The excess and potential backflows for this are shown on the arrows either side of each arc in Figure 3.

State the value of the initial flow.

Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.

Use your answer to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book.

Prove that the answer to part (e) is optimal.

Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

List the saturated arcs.

State the value of the initial flow.

Explain why arc FT cannot be full to capacity.

State the capacity of cut C₁ and the capacity of cut C₂

By inspection find one flow‑augmenting route to increase the flow by three units. You must state your route.

Prove that, once the flow‑augmenting route found in part (e) has been applied, the flow is maximal.

Figure 1 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow.

The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.

Calculate the capacity of

cut C₁

cut C₂

Using only the capacities of cuts C₁ and C₂, state what can be deduced about the maximum flow through the system.

Figure 2 shows an initial flow through the same network.

State the value of the initial flow.

By entering values along BC, CF and DT, complete the labelling procedure on Diagram 1 in the answer book.

Use the labelling procedure to find a maximum flow through the network. You must list each flow‑augmenting route you use, together with its flow.

Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book.

Prove that the answer to (f) is optimal.

A vertex restriction is now applied to B so that no more than 16 litres per second can flow through it.

Complete Diagram 3 in the answer book to show this restriction.

State the value of the maximum flow with this restriction.

Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow.

The weights on the arcs show the lower capacities and upper capacities for the corresponding pipes, in litres per second.

State the source node.

Explain why the sink node must be G.

Calculate the capacity of the cut C₁

Assuming that a feasible flow exists,

(i) explain why arc JH must be at its upper capacity, (ii) explain why arcs AD and CD must be at their lower capacities.

Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system.

Prove that the answer to (e) is the maximum flow through the system.

Two cuts C₁ and C₂ are shown.

Find the capacity of

cut C₁

cut C₂

Explain why the arcs AE and CE cannot be at their upper capacities simultaneously.

Explain why a flow of 31 litres per second through the system is not possible.

Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows.