A-level Mathematics/OCR/D2/Flows in a Network

Weights on arcs are called capacities.
Start of network called the source (S); end of network called the sink (T).
Arcs which are carrying their full capacity are said to be saturated.
A cut is a continuous line that separates S from T and does not pass through any nodes.
With the exception of S and T, the sum of flows into a node must equal sum of flows out of node.
Maximum flow - minimum cut theorem:
- The flow through a network cannot exceed the value of any cut.
- The maximum flow equals the value of the minimum cut.
Meaning that if you can find, by inspection, a flow and a cut which have the same value, then the maximum flow - minimum cut theorem tells you that you have obtained the maximum flow.
Labelling procedure finds the max flow by systematically augmenting any initial flow:

Being with any initial flow or zero flow.
Replace each arc with two arcs: one showing the amount by which the flow can be increased (its excess capacity) and the other showing the amount by which the flow can be decreased (its potential backflow).
If S is still connected to T then find a new flow from S to T and alter the excess capacities and potential backflows as necessary.
Repeat Step 3 until S is disconnected from T.
If S is disconnected from T then the max flow is the sum of all the flows of Steps 1 and 3.

If a network has more than one source, create a new supersource; if it has more than one sink, create a new supersink.
If a node has a restricted capacity then replace it by two unrestricted nodes connected by an arc of the relevant capacity.
For networks where arcs have both upper and lower capacities, the value of a cut is:

the sum of the upper capacities that cross the cut line in the direction from S to T minus the sum of the lower capacities that cross the cut line in the direction from T to S.

For such a network, for the labelling procedure backflows are calculated using the minimum capacities. E.g. for a flow of 5 along an arc with an upper capacity of 8 and a lower capacity of 1, the excess capacity is 3 and the potential backflow is 4.

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.