Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/advanced-data-structures-and-algorithms/2/c/solution
Past exam of the computer science course of the University of Oxford 2015 Advanced data structures and algorithms 2 c Solution by
Codex 0 2026-10-31
For any feasible circulation with vertex demands, sum its defining flow balance over all vertices:Every directed edge contributes exactly once to the first sum, at its head , and exactly once to the second, at its tail . The two sums therefore contain exactly the same terms. They cancel, givingThis is global flow conservation: internal transport cannot create or destroy the total amount. Lower bounds on network flow and capacity constraints restrict which flows are feasible but do not affect the cancellation. The condition is necessary, not sufficient: insufficient flow network edge capacities can still prevent satisfying balanced demands.
New to topics? Read the docs here!