Note: Network flows are not part of the syllabus for IOI/IOITC.
Given a network of pipes with a given capacity and two nodes, source and sink, what is the maximum flow that can be passed from source to sink?
7 -->u ------------->v / \ / \ / 7 \ 10 / \5 / \ / \ source \---- / -->sink \ 10 X / \ 5 / \ /7 \ <------/ \--> / -->w-------------->z 7
In this case, the maximum flow is 12:
Observe that the edges (u,v) and (z,sink) together disconnect the source from the sink. This is called a "cut set". Clearly, any flow that goes from source to sink must go through this cut set and cannot exceed the capacity of the cut, namely 14. There may be many cut sets --- for instance, (source,u), (source,w) is also a cut set, with capacity 12.
It is clear that the maximum flow in the graph cannot exceed the capacity of the minimum size cut in the graph.
Claim: The maximum flow from source to sink is equal to the capacity of the minimum size cut in the graph.
How do we compute the maximum flow?
Suppose we start with a flow
5 5 5 <--flow source---->o---->o---->sink 5 10 5 <--capacity
Now, we select another path (ignoring directions) to augment the flow.
An augmenting path is a path from source to sink where
e.g. we may have a path that looks like
4 6 3 2 <--flow source---->o----->o<-----o<------sink 5 5 4 3 <--capacity
For each edge on this path, we compute leeway(e), defined as:
4 6 3 2 <--flow source---->o----->o<-----o<------sink 5 7 4 3 <--capacity 1 1 3 1 <--leeway
Augment flow upto min leeway along the path. Here min leeway is 1, so you can augment flow. On reverse edges, cancel out the existing flow, so reduce by the augmented amount.
After augmentation.
5 7 2 3 <--new flow source---->o----->o<-----o<------sink 5 7 4 3 <--capacity
Repeat the augmentation step till you cannot find an augmenting path. (This algorithm is called the Ford-Fulkerson algorithm.)
Example:
7 -->u ------------->v / \ / \ / 7 \ 10 / \5 / \ / \ source \---- / -->sink \ 10 X / \ 5 / \ /7 \ <------/ \--> / -->w-------------->z 7
Start with a flow
5 5 5 <--flow source ---->u---->z---->sink 7 10 7 <--capacity
Find an augmenting path, for example:
5 0 0 <--flow source ---->u---->v---->sink 7 7 5 <--capacity 2 7 5 <--leeway
Add flow on this path
7 2 2 <--augmented flow source ---->u---->v---->sink 7 7 5 <--capacity
Now, another augmenting path (with backward edges):
0 0 5 2 2 <--flow source ---->w---->z<----u---->v---->sink 5 7 10 7 5 <--capacity 5 7 5 5 3 <--leeway
Augmented flow
3 3 2 5 5 <--flow source ---->w---->z<----u---->v---->sink 5 7 10 7 5 <--capacity
Finally, we have an augmenting path
3 3 5 <--flow source ---->w---->z---->sink 5 7 7 <--capacity 2 4 2 <--leeway
Augmented flow
5 5 7 <--augmented flow source ---->w---->z---->sink 5 7 7 <--capacity
Add s→w→z→u→v→t
How do we find augmenting paths?
In the worst case, you have to do one iteration for each unit of flow. Let F be the optimum flow. Then, we have F iterations, each of which requires finding an s-t path (BFS/DFS), so it takes mF time. (This assumes that flows are all integers).
Here is a worst case scenario:
10000 10000 --->A---------->t / \ --> / \1 / s --> / 9000 ----------->B 9000
Here, if we always choose a path that includes the edge AB (or BA), each step increases the max flow by exactly 1 unit, so it takes 19000 iterations to terminate. (Of course, we could have been lucky and chosen directly the upper and lower paths to augment.)
Claim: If we always augment the flow by finding the shortest s-t path in terms of number of edges, the algorithm terminates in time O(mn). (We will not prove this). Notice that if we search for augmenting paths via BFS, we are guaranteed to find the shortest augmenting path at each stage.
Observe: If the capacities are integers, each time we augment the flow, we augment it by an integer. So, the max flow will always be integral.
Video lecture on Network flows, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky