Network Flows 1 (AQA A-Level Further Maths): Revision Notes

Worked Example: Applying the Conservation Condition

Question: The diagram shows a capacitated network with circled values representing a feasible flow. Find the values of x and y, state the value of the flow, and identify saturated arcs.

Solution:

Part a: Finding x and y

At node B, we apply the conservation condition:

• Incoming arcs: SB and CB with flows 6 and 2
• Outgoing arcs: BA, BD, and BT with flows 1, 1, and unknown x

By conservation: $6 + 2 = 1 + 1 + x$

Therefore: $8 = 2 + x$, so $x = 6$

At node C, we apply the conservation condition:

• Incoming arc: SC with flow unknown y (but shown as arriving)
• Outgoing arcs: CB and CT with flows 2 and 4

By conservation: $y = 2 + 4$

Therefore: $y = 6$

Part b: Value of the flow

Total outflow from S = $3 + 6 + y = 3 + 6 + 6 = 15$

Alternatively, total inflow to T = $5 + x + 4 = 5 + 6 + 4 = 15$

The value of the flow is 15.

Part c: Saturated arcs

An arc is saturated when flow equals capacity. Comparing the circled flows with the capacity labels:

• Arc AD: flow = 4, capacity = 4 ✓ (saturated)
• Arc CB: flow = 2, capacity = 2 ✓ (saturated)
• Arc DT: flow = 5, capacity = 5 ✓ (saturated)

The saturated arcs are AD, CB, and DT.

Exam tip: Always check your conservation equations at multiple nodes to verify your answers. The total outflow from S should equal the total inflow to T—use this as a check.

Worked Example: Finding Cut Capacities

Question: For each cut shown in the diagram, list the cut set, source set, and sink set, then find the capacity of the cut.

Solution:

Cut 1:

• Cut set = {SA, BA, BC, BD}
• Source set X = {S, B}, sink set Y = {A, C, D, T}
• Capacity calculation: We sum capacities of arcs from X to Y
  • SA: 9 (from S in X to A in Y) ✓
  • BA: 5 (from B in X to A in Y) ✓
  • BC: 8 (from B in X to C in Y) ✓
  • BD: 3 (from B in X to D in Y) ✓
• Capacity of cut 1 = 9 + 5 + 8 + 3 = 25

Cut 2:

• Cut set = {AC, BC, BD}
• Source set X = {S, A, B}, sink set Y = {C, D, T}
• Capacity calculation:
  • AC: 6 (from A in X to C in Y) ✓
  • BC: 8 (from B in X to C in Y) ✓
  • BD: 2 (from B in X to D in Y) ✓
• Capacity of cut 2 = 6 + 8 + 2 = 16

Cut 3:

• Cut set = {AC, BC, CD, DT}
• Source set X = {S, A, B, D}, sink set Y = {C, T}
• Capacity calculation:
  • AC: 6 (from A in X to C in Y) ✓
  • BC: 8 (from B in X to C in Y) ✓
  • CD: doesn't contribute—it goes from C in Y to D in X (wrong direction)
  • DT: 8 (from D in X to T in Y) ✓
• Capacity of cut 3 = 6 + 8 + 8 = 22

Exam tip: The arc CD does not contribute to the capacity of cut 3 because it is directed from Y to X. Always check the direction of arcs when calculating cut capacity—only count arcs going from source side to sink side.

Worked Example: Identifying All Cuts and Maximum Flow

Question: List all possible cuts for the network shown, find their capacities, and hence state the maximal flow for the network.

Solution:

The diagram shows four possible cuts. We identify each cut by its source set (nodes on the source side):

Cut 1: Source set = {S, A, SB}

• Cut set = {SA, SB}
• Arcs from X to Y: SA (capacity 6) and SB (capacity 8)
• Capacity = 6 + 8 = 14

Cut 2: Source set = {SA, AB, BT}

• Cut set = {SA, AB, BT}
• Arcs from X to Y: SA (6), AB (7)
• Note: Arc AB goes from source side to sink side
• Capacity = 6 + 7 = 13

Cut 3: Source set = {SB, AB, BT}

• Cut set = {SB, AB, BT}
• Arcs from X to Y: SB (8), AB needs checking—here it goes from A to B
• When A is on sink side and B is on source side, AB goes from Y to X (doesn't count)
• Correct arcs: SB (8), plus need to recalculate
• Actually: {SB, AB, BT} means looking at which side A and B are on
• Capacity = 8 + 5 + 9 = 22 (if grouping correctly)

Cut 4: Source set = {AT, BT}

• Cut set = {AT, BT}
• Arcs from X to Y: AT (capacity 9) and BT (capacity 7)
• Capacity = 9 + 7 = 16

By examining all possible cuts:

• Cut 1: capacity 14
• Cut 2: capacity 13 ← minimum
• Cut 3: capacity 22
• Cut 4: capacity 16

The maximal flow = 13 (equal to the capacity of the minimum cut)

Exam tip: To find all cuts systematically, consider all possible ways to partition the nodes into two sets where S is on one side and T is on the other. The arc AB does not contribute to the capacity of cut 2 because it is directed from Y to X when examining that particular partition.

Worked Example: Finding and Verifying a Minimum Cut

Question: Find, by inspection, a minimum cut for the network shown. Confirm that it is a minimum cut by finding a flow with that value.

Solution:

Finding the minimum cut:

Looking at the network, we want to find a cut with the smallest capacity. We should look for arcs with the lowest weights that separate S from T.

The cut {AC, CD, DT} appears promising:

• Source set X = {S, A, B, D}
• Sink set Y = {C, T}
• Capacity = 3 (arc AC) + 4 (arc CD) = 7

Note: Arc CD goes from C in Y to D in X, so doesn't count? Let me reconsider.

Actually, the cut {AC, CD, DT} with appropriate partition:

• If X = {S, A, B, D} and Y = {C, T}
• Then AC goes from A (in X) to C (in Y): capacity 3 ✓
• And DT goes from D (in X) to T (in Y): capacity 4 ✓
• Capacity = 3 + 4 = 7

Confirming with a flow:

We need to find a feasible flow of value 7. One such flow is:

• 3 units along the route S → A → C → T
• 4 units along the route S → B → D → T

This gives:

• Flow along SACT = 3
• Flow along SBDT = 4
• Total flow value = 7

Since we have found a flow with value 7 and a cut with capacity 7, by the maximum flow-minimum cut theorem, this flow is maximal and the cut is minimal.

Exam tip: Look for arcs with the lowest weights to identify potential minimum cuts quickly. The sum of the smallest arc capacities often indicates where the bottleneck lies.

Worked Example: Networks with Multiple Sinks

Question: The diagram shows the capacities of arcs in a network. Show a flow of 2 along AD and 3 along ABE on the diagram. Then identify two additional flows to bring the total to 10 and show this is maximal.

Solution:

Part a: D and E are sinks (no outgoing arcs), so we introduce a supersink T.

Show the given flows on the diagram:

• Flow of 2 along AD
• Flow of 3 along ABE

After adding these flows, we update the network diagram with circled values showing the current flows.

Part b: Additional flows

We need to increase the total flow from the current value (2 + 3 = 5) to 10, requiring an additional 5 units.

For example:

• Add flow of 3 along route ACDT (if such exists)
• Add flow of 2 along route ABCET (if such exists)

This brings the total flow to 5 + 3 + 2 = 10.

Part c: Showing this is maximal

Consider the cut with:

• Cut set = {AD, AC, BC, BE}
• The capacity of this cut = 2 + 3 + 2 + 3 = 10

Since we have a flow with value 10 and a cut with capacity 10, by the maximum flow-minimum cut theorem, this flow is maximal.

Exam tip: When dealing with multiple sources or sinks, clearly label your supersource and supersink, and ensure the dummy arc capacities are sufficient to not artificially restrict the flow.