Multiple sources and sinks, restricted capacities and optimal flow 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 a super source?
- An added vertex joined to every source, so that the network has one source.
- What capacity goes on each arc from the super source?
- The supply of the source it joins.
- What capacity goes on each arc to the super sink?
- The demand of the sink it comes from.
- How do you model a vertex with restricted capacity ?
- Split it into and joined by an arc of capacity .
- Where do arcs go when a vertex is split?
- Arcs into end at ; arcs out of start at .
- What does on an arc mean?
- The flow must be at least and at most .
- Forward label on an arc with lower and upper capacities?
- Upper capacity minus flow.
- Backward label on an arc with lower and upper capacities?
- Flow minus lower capacity.
- Capacity of a cut with lower capacities?
- Sum of upper capacities from to minus sum of lower capacities from to .
- When is a flow feasible?
- When every arc has lower flow upper and flow in = flow out at each intermediate vertex.
- Which arcs should you change to increase the maximum flow?
- Those in the minimum cut.
- Why might the maximum flow stop rising after an improvement?
- Another cut becomes the smallest cut.