Vertex restrictions in networks

A question is this type if and only if it involves a restriction on flow through a vertex (not just arcs), requiring network modification to model this constraint.

3 questions · Standard +0.6

7.04e Route inspection: Chinese postman, pairing odd nodes
Sort by: Default | Easiest first | Hardest first
OCR D2 2010 January Q6
14 marks Challenging +1.2
6 The diagram represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows two cuts, \(\alpha\) and \(\beta\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}
  1. Calculate the capacities of the cuts \(\alpha\) and \(\beta\).
  2. Explain why the arcs \(A C\) and \(A F\) cannot both be at their lower capacities.
  3. Explain why the \(\operatorname { arcs } B C , B D , D E\) and \(D T\) must all be at their lower capacities.
  4. Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working. Vertex \(E\) becomes blocked so that no fluid can flow through it.
  5. Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.
Edexcel FD2 2024 June Q1
10 marks Standard +0.3
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{931ccf1d-4b02-448c-b492-846b0f42c057-02_696_1347_214_367} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 shows a capacitated, directed network of pipes. The numbers in circles represent an initial flow from S to T . The other number on each arc represents the capacity, in litres per second, of the corresponding pipe.
    1. State the value of \(x\)
    2. State the value of \(y\)
  2. State the value of the initial flow.
  3. State the capacity of cut \(C _ { 1 }\)
  4. Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route. The flow-augmenting route from (d) is used to increase the flow from S to T .
  5. Prove that the flow is now maximal. A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
    1. Complete Diagram 1 in the answer book to show this restriction.
    2. State the value of the maximum flow through the network with this restriction.
OCR D2 Q2
8 marks Standard +0.3
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d88fdf1e-7547-434d-ba87-7f816e4386ba-1_627_1116_1190_388} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the maximum capacity of that arc. In addition to the restrictions on flow through the arcs a maximum flow of 6 units is allowed to pass through vertex \(C\).
  1. Redraw the network to take into account this restriction.
  2. Starting with an initial flow of 6 units along SADT and 6 units along SBT use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.