Flows, cuts and the max-flow min-cut theorem Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
13 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 13 cards
- What is a flow network?
- A network of directed arcs with capacities, a source where flow enters and a sink where it leaves.
- State the two rules for a feasible flow.
- Flow on each arc is at most its capacity (and non-negative), and flow in equals flow out at every intermediate node.
- What is the value of a flow?
- The total flow leaving the source, which equals the total flow arriving at the sink.
- What does it mean for an arc to be saturated?
- Its flow equals its capacity.
- What is a cut?
- A division of the nodes into two sets, one containing the source and one containing the sink.
- How is the capacity of a cut found?
- Add the capacities of the arcs directed from the source side to the sink side.
- Are arcs directed from the sink side to the source side counted in a cut?
- No. Only arcs leaving the source set are counted.
- Compare any flow with any cut.
- The value of any flow is at most the capacity of any cut.
- State the max-flow min-cut theorem.
- In any network the value of the maximum flow equals the capacity of the minimum cut.
- How do you prove a flow is maximal?
- Find a cut whose capacity equals the flow value, then quote the max-flow min-cut theorem.
- When does raising an arc's capacity increase the maximum flow?
- Only if the arc lies in every minimum cut.
- What is a supersource and how is it joined?
- A single added source, with an arc from it to each real source; each arc has the capacity of the supply.
- What is a supersink and how is it joined?
- A single added sink, with an arc into it from each real sink; each arc has the capacity of the demand.