List saturated arcs

A question is this type if and only if it asks to identify which arcs are at full capacity (saturated) given a flow pattern.

3 questions · Moderate -0.8

7.04e Route inspection: Chinese postman, pairing odd nodes
Sort by: Default | Easiest first | Hardest first
Edexcel D2 2016 June Q2
8 marks Easy -1.2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a12f9520-85c0-43f6-a104-2502011d5657-3_780_1155_246_461} \captionsetup{labelformat=empty} \caption{Figure 1}
\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 an initial flow.
  1. List the saturated arcs.
  2. State the value of the initial flow.
  3. State the capacities of the cuts \(C _ { 1 }\) and \(C _ { 2 }\)
  4. By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route.
  5. Prove that the new flow is maximal.
Edexcel FD2 AS 2022 June Q2
9 marks Moderate -0.5
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d7e250dc-9e38-4f65-a51a-c6a08082f310-03_1120_1757_212_153} \captionsetup{labelformat=empty} \caption{Figure 1}
\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. State the value of this flow.
  2. List the eight saturated arcs.
  3. Explain why arc EH can never be full to capacity.
  4. Find the capacity of
    1. cut \(C _ { 1 }\)
    2. cut \(C _ { 2 }\)
  5. Write down a flow-augmenting route that increases the flow by three units. Given that the flow through the network is increased by three units,
  6. prove that this new flow is maximal.
Edexcel FD2 2022 June Q4
9 marks Moderate -0.8
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{cea07472-f93b-4a7b-b362-89fb8c0af4a9-04_931_1312_219_379} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} 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.
  1. List the saturated arcs.
  2. State the value of the initial flow.
  3. Explain why arc FT cannot be full to capacity.
  4. State the capacity of cut \(C _ { 1 }\) and the capacity of cut \(C _ { 2 }\)
  5. By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
  6. Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.