Exam Format & Expectations
Flow algorithm questions typically ask you to:
- Execute algorithm steps - Run Ford-Fulkerson or Edmonds-Karp
- Find augmenting paths - BFS for shortest path in residual network
- Identify critical edges - Which edges become saturated?
- Calculate flow changes - How does flow change after augmentation?
Past Exam Example: Edmonds-Karp Execution (2024)
Given Network:
Current flow f with value |f| = 10:
- f(s,a) = 8, f(s,b) = 2
- f(a,b) = 0, f(a,t) = 8
- f(b,t) = 2
Question 4a: Find the shortest augmenting path in Gf
Step 1: Construct residual network Gf:
Step 2: Run BFS from s to t:
Shortest augmenting path: s → a → b → t
Bottleneck capacity: min{2, 2, 8} = 2
Question 4b: Which edges become critical after augmentation?
Definition: An edge is critical if it becomes saturated (residual capacity = 0) after augmentation.
After augmenting by 2 units along s → a → b → t:
- f'(s,a) = 8 + 2 = 10 → cf'(s,a) = 0 ✓ Critical
- f'(a,b) = 0 + 2 = 2 → cf'(a,b) = 0 ✓ Critical
- f'(b,t) = 2 + 2 = 4 → cf'(b,t) = 6 ✗ Not critical
Answer: Edges (s,a) and (a,b) become critical.
Question 4c: What is the new inflow at vertex b after augmentation?
Definition: inflow(v) = Σu f(u,v)
After augmentation:
- f'(s,b) = 2 (unchanged)
- f'(a,b) = 2 (increased from 0)
inflow(b) = f'(s,b) + f'(a,b) = 2 + 2 = 4
Key Concepts to Master
Residual Network
For each edge (u,v) with capacity c and flow f:
- • Forward: cf(u,v) = c(u,v) - f(u,v)
- • Backward: cf(v,u) = f(u,v)
Only include edges with positive residual capacity!
Critical Edges
- 1. Find all residual capacities on path
- 2. Bottleneck = minimum capacity
- 3. Critical = edges with capacity = bottleneck
- 4. Can have multiple critical edges!
Inflow Analysis
inflow(v) = Σu f(u,v)
After augmentation:
• Check each vertex on path
• Account for reversed edges
Algorithm Differences
Edmonds-Karp:
• Uses BFS for shortest path
• O(VE²) time complexity
Ford-Fulkerson:
• Any augmenting path
• May not terminate with irrational capacities
Common Mistakes to Avoid
Calculation Errors
- • Using original network instead of residual
- • Forgetting backward edges exist
- • Wrong residual capacity formula
- • Missing some critical edges
Conceptual Errors
- • Confusing flow value with edge flow
- • Not checking all paths for alternatives
- • Assuming unique shortest path
- • Forgetting capacity constraints
Pro tip: Always draw the residual network clearly. Label each edge with its residual capacity. This prevents most errors.