Find flow-augmenting route by inspection

A question is this type if and only if it asks to identify a specific flow-augmenting path and its capacity without using the full labelling procedure.

2 questions · Moderate -0.5

Sort by: Default | Easiest first | Hardest first
Edexcel FD2 AS 2024 June Q1
8 marks Moderate -0.5
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{40023f8e-6874-400e-84b5-60d98b648afc-02_1010_1467_353_399} \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.
    (1)
  2. Explain why arcs CD and CG cannot both be saturated.
    (1)
  3. Find the capacity of
    1. cut \(C _ { 1 }\)
    2. cut \(C _ { 2 }\)
  4. Write down a flow augmenting route of weight 6 which saturates BF. The flow augmenting route in part (d) is applied to give an increased flow.
  5. Prove that this increased flow is maximal.
Edexcel FD2 2023 June Q1
7 marks Moderate -0.5
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ae354c58-6de8-4f94-b404-2f0feecb5bf3-02_953_1687_251_191} \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 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)