Ford Fulkerson Method for Maximum Flow in graphs

__Ford Fulkerson Method for Maximum Flow__

__Network Flow __

∑_{y∈V}(x,y) = 0 = ∑_{y∈V}(y,x) ∀ x∈V-{s,t} where ‘V’ is a set of all vertices

f(s,y) ≥ 0 ∀ y

f(y,t) ≥ 0 ∀ y

_{f}as :

C_{f}(x,y)= C(x,y) – f(x,y).

If C_{f}(x,y) = 0 then, we say that edge (x,y) is saturated because we cannot send more flow through this edge. Let U and W be the subsets of V, then flow f(U,W) is donated by sum of the flow of all the edges with one vertex in U and the other one in W.

f(U, W) = ∑_{x∈U}∑_{y∈W}f(x,y)

The figure shows the graph of the network flow.Note that the flow in all the vertices other than source and the sink is conserved i.e. net flow going into a vertex is equal to the net flow coming out of the vertex.

**Cut**

C = (S, V-S) such that s∈S, t∈(V-S)

**Edge Set**E

**of a cut is the set of all the edges such one of the vertex of the edge is in S and the other one is in V-S. It contains the edges that point form the set containing the source to the set containing the sink. Therefore**

**Capacity C of a cut (S, V-S)**is the sum of capacities of all the edges of the in the Edge set of the cut.

**Property A :**An Edge Set E’⊂E (where E is the complete set of edges) is an edge set of a cut if and only if E’ is the minimal set with the property that any path from source ‘s’ to sink ‘t’ passes through atleast one edge of E’. Here, by “minimal” i mean to say that this property breaks down if even one edge of E’ is withdrawn.

**Proof :**Let us say E’ is the edge set of some cut (S, V-S). Now, let us take some arbitrary path from source s to sink t. The figure below shows the path from s to t.

**s, x, y, t**. In this path, edge (s, x)∈S and edge (y, t)∈(V-S). It is clear that neither of the edges (s,x) and (y, t) belongs to the edge set of the cut and since edge (x,y) also does not belong to the edge set, the edge set E” fails to satisfy the property because now there exists a path the does not pass through the edge set. Hence, E’ is a minimal set having the Property A.

**Net Flow**

The above result states that whatever net flow has emerged out of the source ‘s’ is equal to the net flow that goes from S to (V-S).

**Problem**

**Max flow Min Cut Theorem.**

**Max flow Min Cut Theorem :**This theorem states that if ‘f ‘ is the maximum flow for a given network, then the value of the flow |f| is the minimum cut capacity.

**s, x1, x2 ….., xk, t,**such that none of the edges of E1 are in the path. So, every edge in E1 has some greater than zero residual capacity. Let ‘r’ be the minimum of all the residual capacities in path P. Then every flow ‘f ‘ in every edge can be increased to f ‘ by ‘r’. So,

This tells us that as long as there is room for some improvement in the flow, or we can say that the flow is not maximum, there exists a path from source ‘s’ to sink ‘t’. Note that by saying that there exists a path from source ‘s’ to sink ‘t’, we mean that there is no saturated edge in the path.

**Residual Graph**

**Augmenting Path**“. So, the flow will be maximum if and only if the residual graph has no path form source ‘s’ to sink ‘t’.

## Ford-Fulkerson Method

### Complexity Analysis

**O(E*f)**where ‘E’ is the number of edges in the graph and ‘f’ is the maximum flow in the graph. This is because each augmenting path can be found in O(E) time and increases the flow by an integer amount by atleast 1.

**O(VE**

^{2}).**The code of the algorithm will be added later.**