Augmenting flows and refinements Quiz

1. An arc has capacity 9 and carries a flow of 5. What are its spare capacity forwards and the amount that can be cancelled backwards?

• A. 4 forwards and 5 backwards
• B. 5 forwards and 4 backwards
• C. 9 forwards and 5 backwards
• D. 4 forwards and 4 backwards

2. An arc has limits $[2,6]$ and carries a flow of 5. By how much can its flow be reduced using a backward move?

• A. $5$
• B. $1$
• C. $4$
• D. $3$

3. Node $X$ can pass at most 8 units per hour in total. How is this modelled?

• A. Reduce every arc into $X$ to capacity 8
• B. Split $X$ into two nodes joined by an arc of capacity 8
• C. Add an arc of capacity 8 from the source to $X$
• D. Delete $X$ and join its neighbours directly

4. How can you tell the augmenting algorithm has finished?

• A. The flow value is an even number
• B. Every arc is saturated
• C. The sink has no arcs entering it
• D. No augmenting route from the source to the sink exists

5. The arcs from $X$ to $Y$ have upper capacities totalling 15, and one arc from $Y$ to $X$ has a lower capacity of 2. What is the capacity of the cut?

• A. $15$
• B. $17$
• C. $13$
• D. $2$