Network flows Flashcards
What does a network flow problem involve?
Finding the maximum possible continuous flow from a source to a terminus through a network of routes, along each of which the flow rate is restricted.
When showing a capacitated directed network, which numbers should be circled?
The flow of each arc.
The capacity of each arc should NOT be circled.
What does it mean if an arc is saturated?
The flow through the arc is equal to its capacity.
What is a source node?
A node where all flows start from.
What is the name for the node where all flows end?
The terminus.
What is a cut?
A partition of the nodes into a set containing the source, and a set containing the terminus.
What is the value of a cut?
The sum of the capacities of cut arcs.
ONLY arcs going from the source set TO the sink set should be counted.
How should the value of a cut be determined if arcs have both an upper and lower capacity?
Sum of the max capacities of arcs flowing from the source to terminus, MINUS the sum of the min capacities of the arcs flowing from the terminus to the source.
What is the maximum flow-minimum cut theorem?
The maximum flow through a network is equal to the minimum cut value.
What is the potential increase of an arc?
The amount by which the flow in an arc can be increased without exceeding its capacity.
What is the potential decrease of an arc?
The amount by which the flow through an arc can decrease, without being lower than its minimum capacity.
What method can be used to augment the flow through a network, so that the flow reaches its maximum value?
The labelling procedure (flow augmentation).
What are supersources/sinks used for?
When a network has multiple sources/sinks.
How can the capacity of arcs connecting an added supersource/sink be calculated?
Equal to the sum of the capacities of the arcs leaving that source. (minimum and maximum calculated separately)
How should a node with a restricted capacity be added to the labelling procedure?
Separate into two nodes connected by an arc of that capacity.
