CO351 Study Guide - Final Guide: Flow Network, Minimum Cut, Seating Capacity

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO351
• Professor: Pei

Document Summary

[10 marks] consider a digraph d = (n, a) with non-negative arc-capacities, and distinct nodes s, t n . Let x and x be feasible st- ows in d where x is obtained by pushing ow along a shortest augmenting path in the residual digraph dx. Further, suppose that the distance from s of every node u in the two residual digraphs dx, dx is the same. I. e. , dx(u) = dx (u) for all u n . Let a+ x be the set of arcs uv in the residual digraph dx such that dx(v) = dx(u) + 1. I. e. , a+ x is the set of arcs from one level of a bfs tree rooted at s to the next. Prove that (cid:12)(cid:12)a+ x (cid:12)(cid:12) < |a+ x |. (this shows that in every iteration of the ford-fulkerson algorithm with the edmonds-karp rule, either the distance label of some node increases or the number of arcs in a+ x decreases.