Network Flow and the Max-Flow Min-Cut Theorem · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Push water, find the bottleneck

Computing · Algorithms & Data Structures · ages 21-22
Name ______________________   Date ____________

  1. What does the max-flow min-cut theorem say about the two numbers?

    • The two numbers are always equal
    • The flow is always double the cut
    • The cut is always zero

  2. What limits how much one edge can carry?

    • Its length on screen
    • Its capacity
    • Its colour

  3. A residual graph shows leftover room on every edge.

    Circle one:   True   False

  4. No augmenting path remains in the residual graph. What do you know?

    • The network has no edges at all
    • All capacities must be doubled
    • Maximum flow, cut found

  5. Source edges hold 4 and 3, sink edges hold 3 and 5, and middle links never bind. What is the maximum flow? Type the number.

    Answer: ______________

  6. To match workers to jobs as a flow, what capacities do you use?

    • Infinite on every edge
    • One on every edge
    • Zero on every edge

  7. A matching flow pairs Ana to job X through a used middle edge. The boss asks why Ana cannot also take job Y. What is the answer?

    • Middle edges forbid all other pairings
    • The sink rejected her name
    • Her 1-capacity edge is spent

  8. Your flow is 6 but you find a cut of cost 5. What must be true?

    • Mismeasured, flow cannot beat a cut
    • The theorem is broken for this network
    • The residual graph needs deleting
LightMySky · lightmysky.comW1-mt_momRV9lK1n-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Push water, find the bottleneck W1-mt_momRV9lK1n-s1

  1. The two numbers are always equal · Maximum flow and cheapest cut agree every time.
  2. Its capacity · Flow on an edge may never exceed its capacity.
  3. True · That working map is what each new path is found on.
  4. Maximum flow, cut found · Exhausted room means optimal flow, with the cut on display.
  5. 7 · The source caps the total at 7, and the sink can take it.
  6. One on every edge · Unit capacities make each pairing count exactly once.
  7. Her 1-capacity edge is spent · Unit capacity lets each worker out once, so she is booked.
  8. Mismeasured, flow cannot beat a cut · No flow beats its cheapest cut, so one of your numbers is off.
Worksheet · LightMySky