Apply labelling procedure for max flow

A question is this type if and only if it asks to use the labelling/flow augmentation procedure to find maximum flow, listing flow-augmenting routes and their flows.

5 questions · Moderate -0.2

7.04e Route inspection: Chinese postman, pairing odd nodes
Sort by: Default | Easiest first | Hardest first
Edexcel D1 Q6
16 marks Moderate -0.3
6. The table below shows the maximum flows possible within a system.
To From\(S\)\(A\)\(B\)\(C\)D\(T\)
S-353055--
A-----50
B-12-8-20
C----1530
D-----14
T------
For example, the maximum flow from \(B\) to \(A\) is 12 units.
  1. Draw a digraph to represent this information.
  2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
  3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
  4. Use the labelling procedure to find the maximum flow from \(S\) to \(T\). You should list each flow-augmenting route you find together with its flow.
  5. Explain how you know that you have found the maximum possible flow.
  6. Give an example of a practical situation that could be modelled by the original table.
Edexcel D1 Q4
11 marks Standard +0.3
4. The following matrix gives the capacities of the pipes in a system.
To FromS\(T\)A\(B\)\(C\)D
S--1626--
T------
A----135
B-16---11
C-11----
D-11----
  1. Represent this information as a digraph.
  2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
  3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
  4. Explain how you know that this flow is maximal.
Edexcel D2 2013 June Q3
10 marks Standard +0.3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{f3feef8a-32ba-4234-a5fa-cdd26ef6967d-4_778_1420_262_360} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 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.
  2. State the capacity of cut \(\mathrm { C } _ { 1 }\). The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.
  3. Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
    (4)
  4. Draw a maximum flow pattern on Diagram 2 in your answer book.
    (2)
  5. Prove that the flow shown in (d) is maximal.
    (2)
OCR D2 2007 January Q5
12 marks Moderate -0.5
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}
Edexcel D2 Q8
14 marks Moderate -0.8
\includegraphics{figure_4} 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. [2]
\includegraphics{figure_5} Figure 5 shows a feasible flow through the same network.
  1. State the value of the feasible flow shown in Fig. 5. [1]
Taking the flow in Fig. 5 as your initial flow pattern,
  1. 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. [6]
  2. Show the maximal flow on Diagram 2 and state its value. [3]
  3. Prove that your flow is maximal. [2]