CS 163/265, Winter 2025, Practice Problem Set 8

For the flow network below, for maximum flows from s to t, with the capacities shown:

A graph with four vertices s, a, b, and t. There are edges with capacities 3 from s to a, 6 from s to b, 2 from a to b, 5 from b to a, 7 from a to t, and 4 from b to t.

  1. Find the sequence of flows and residual graphs that would be found by repeatedly augmenting on unweighted shortest residual paths (the residual paths with the smallest numbers of edges). When you have a choice for which path to choose, you may choose any shortest path.

  2. Find the sequence of flows and residual graphs that would be found by repeatedly augmenting on widest residual paths (the residual paths with the largest capacity). When you have a choice for which path to choose, you may choose any widest path.

  3. This flow network has two minimum cuts. Which vertices are separated by these cuts? Which one would be found by the method for converting a maximum flow into a minimum cut described by the lecture notes (on the slide labeled "If this algorithm terminates it finds a minimum cut")?

  4. As in several other examples we have seen, this flow network includes a pair of edges that connect the same two vertices in opposite directions: one edge is directed from a to b while the other is directed from b to a. Suppose we have a network with a pair of edges like this, and a maximum flow that uses both of these edges, with flow amounts fab on the edge from a to b and fba on the edge from b to a. Describe how to find another maximum flow that uses at most one of these two edges, and has zero flow on the other edge.