Multiple sources and sinks, restricted capacities and optimal flow

Multiple sources and sinks, restricted capacities and optimal flow Flashcards

Spec 3.4–5 · Edexcel A-Level Further Maths: 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 CC with restricted capacity kk?
Split it into CinC_{\text{in}} and CoutC_{\text{out}} joined by an arc of capacity kk.
Where do arcs go when a vertex is split?
Arcs into CC end at CinC_{\text{in}}; arcs out of CC start at CoutC_{\text{out}}.
What does [3,8][3, 8] on an arc mean?
The flow must be at least 33 and at most 88.
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 XX to YY minus sum of lower capacities from YY to XX.
When is a flow feasible?
When every arc has lower ≤\le flow ≤\le 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.

Flashcards