State initial flow value

A question is this type if and only if it asks to calculate the total value of a given initial or feasible flow from source to sink.

2 questions · Easy -1.2

7.04e Route inspection: Chinese postman, pairing odd nodes
Sort by: Default | Easiest first | Hardest first
Edexcel D2 2007 June Q9
10 marks Easy -1.2
9. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-7_931_1651_196_118} \captionsetup{labelformat=empty} \caption{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.}
\end{figure}
  1. State the value of the initial flow.
  2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\). Figure 2 shows the labelling procedure applied to the above network.
  3. Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
  4. Prove that the flow is now maximal. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure}
Edexcel D1 2008 June Q5
11 marks Easy -1.2
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-5_819_1421_251_322} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 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.