Cuts, labelling procedure and max-flow min-cut Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What is the capacity of a cut?
- The sum of the capacities of the arcs directed from to (arcs from to are ignored).
- What do the sets and of a cut contain?
- contains the source S and contains the sink T.
- What two rules must a feasible flow obey?
- Flow on each arc is between and its capacity, and flow in equals flow out at every vertex other than S and T.
- What is the value of a flow?
- The amount leaving the source, which equals the amount entering the sink.
- In the labelling procedure, what does the arrow in the direction of the arc show?
- The amount by which the flow can be increased (capacity minus flow).
- What does the arrow in the opposite direction show?
- The amount by which the flow could be reduced (the current flow).
- What is a flow-augmenting route?
- A route from S to T along which the flow can be increased.
- By how much is the flow increased on a route?
- By the smallest number on the route.
- What happens on a backward arc of a route?
- The flow in that arc is reduced by the amount.
- State the max-flow min-cut theorem.
- The value of a maximum flow equals the capacity of a minimum cut.
- How do you prove a flow is maximum?
- Find a cut whose capacity equals the flow value.
- When does the labelling procedure stop?
- When T cannot be labelled, so no further augmenting route exists.