Unit 4 extends network analysis to larger, multi-stage problems that combine several algorithms and require careful interpretation. Common complex scenarios include:
In a directed network with capacities, the maximum flow problem asks: what is the greatest amount that can flow from source $S$ to sink $T$?
Max-flow min-cut theorem: The maximum flow equals the capacity of the minimum cut (the minimum total capacity of edges whose removal disconnects $S$ from $T$).
Network with capacities (litres/min): $S \to A$: 8, $S \to B$: 6, $A \to T$: 5, $A \to B$: 3, $B \to T$: 7.
Possible cuts:
- ${S \to A, S \to B}$: capacity \$8 + 6 = 14$
- ${A \to T, B \to T}$: capacity \$5 + 7 = 12$
- ${A \to T, A \to B, S \to B}$: capacity \$5 + 3 + 6 = 14$
Minimum cut = ${A \to T, B \to T}$ = 12 litres/min. Maximum flow = 12 litres/min.
Extended critical path problems may include:
- Multiple resources (workers, equipment) with constraints
- Crashing (reducing activity duration at extra cost)
- Resource levelling (distributing workload evenly)
For VCAA level, focus on identifying EST, LST, float, and the critical path in a larger activity network.
Some problems require:
1. Finding a minimal spanning tree (connect depots cheaply)
2. Then finding the shortest path between specific nodes in that tree
Read the question carefully to identify which algorithm applies to which part.
VCAA FOCUS: Complex network questions in extended response ask for algorithm steps, identification of optimal routes/assignments, and contextual interpretation. Marks are assigned to each step — show all working.
STUDY HINT: Practise drawing neat, labelled network diagrams. Errors in diagrams propagate through all subsequent calculations. Use a ruler and label all edges with their weights.
