Cost minimal maximum flow in graphs: Ford-Fulkerson 1
'Fold-Fulkerson-Method
I. Theory
In graph theory the determination of the maximum flow in networks plays an important aspect. This can be seen on the practical use of the graph theory. In reality the maximum flow is mostly complemented with the cost minimum criterion. In this Wiki we shall give you a profound overview how the algorithm created by Lester Randolph Ford Junior and Delbert Ray Fulkerson works. The Ford-fulkerson method is an iterative process to determine the max flow in a network.
The theorem of Min Cut - Max Flow implies that the maximum flow is equal to the capacity sum of the cut with minimal capacity. Aiming to find the optmial solution you may have to do following steps:
1. Determine the cost minimal route from the source node to the sink node which still has capacity. If there is no route left, then you can stop.
2. If not, then add the highest possible flow to the selected route and continue with the first step.
II. Terminology
A network flow is a graph with a set of vertices and a set of edges . An edge is a connection between one or two vertices in a graph. Each edge Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (u,v)\in E
has a capacity Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c(u,v)\geq 0
. We will assume that in a flow network with source and sink , for any vertex Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v\in V
there is a path from to that passes through .
A flow in a flow network with source and sink is a function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f:V\times V \rightarrow R
that satisfies the following properties:
1. Capacity Constraint: For all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u,v\in V, f(u,v)\leq c(u,v)
2. Skew Symmetry: For all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u,v\in V,f(u,v)=\ - f(v,u)
3. Flow Conservation: If Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u,v\in V
and , then Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{v\in V}f(u,v]=0
is the flow from vertex to vertex
For the better understandig of the algorithm and its terminology, we will give you an example.
Example
Starting source node is number 1 and sink node is number 4.
The cost minimum path goes through the nodes 3 and 2 with a maximum Flow of 2 and costs of 18.
Another cost minimum path goes through the node 2 with a maximum flow of 2 and cost of 10 units. The path between the nodes 1 and 3 is sorted out because the capacity of this path has already been reached. Moreover, the cost of a flow from node 2 to node 3 is -3, because a flow in this direction is tantamount to the decrease of the flow from node 3 to node 2.
Another possible path is 1-2-3-4. The paths 1-3 and 2-4 are not available anymore, because their capacity has been reached. The cost per unit is 11. The flow in this way means an increase of the flows from node 1 to node 2 and node 3 to node 4. But the flow from 2 to 3 will be balanced by the flow from 3 to 2.
A new calculated path goes again through the nodes 2 and 3, but now with costs of 17 (6+3+8) per unit. There are no more residual capacity in the edges. So we have reached the maximum flow with the minimum cost, as we can see on the following table.
Source:
- H. Müller-Merbarch (1973): Operations Research - Brossard Elliot (2010): Graph Theory: Network Flow, Term Paper, Washington University - or skript 2013
