Flow Networks

Maxim um Fl ow Netw ork s

CONTENTS 

Network flows on directed acyclic graphs



Ford-Fulkerson Algorithms -Residual networks



Min cut Max flow theorem



Max Bipartite matching

Network flows on directed acyclic graphs 

DAG is a directed graph with no cycles.



Flow network: a flow network G = (V,E) is a directed graph in which each edge (u,v) ∈ E has a nonnegative capacity c(u,v) >= 0. if (u,v) ∉ E , we assume that c(u,v) = 0.

 

We distinguish two vertices in flow network , source s and sink t. The source produces the material at a steady rate . The sink consumes the material at a steady rat Objective : how much of material can be imposed through network that network can handle



Flow: A flow in G is a real-valued function f : V × V → R that satisfies three properties:

1. Capacity constraint : For all u,v ∈ V, we require f(u,v) ≤ c(u,v). The net flow from one vertex to another must not exceed the given capacity. 2. Skew symmetry : For all u,v ∈V, we require f(u,v) = -f(v,u). The net flow from a vertex u to a vertex v is the negative of the net flow in the reverse direction 3. Flow conservation : For all u ∈ V - {s,t}, we require ∑ f(u,v) = 0. v ∈V The quantity f(u,v),which can be positive or negative , is called the net flow from vertex u to v. The value of the flow is defined as | f | = ∑ f(s,v) that is the totat net Flow out of the source. v ∈V

Residual Networks 



Given a flow network and a flow, residual network consists of edges that can admit more flow. The amount of additional flow that can be pushed from u to v before exceeding the capacity c(u,v) is the residual capacity of (u,v), given by Cf(u,v) - f(u,v)



Given a flow network G=(V,E) and a flow f, the residual network of G induced by f is Gf=(V,E) and a flow f, the Residual Network of G Ef={(u,v) V×V : cf(u,v)>0} That is, each edge of residual network , or residual edge, can

Augmenting Paths 

Given a flow network and a flow f, an augmenting path p is a simple path from s to t in the residual network Gf .



Residual capacity of path p is defined as the maximum amount by which we can increase the flow on each edge of p, given by cf(p)=min{cf(u,v) : (u,v) is on p}





 

Cut(S,T) of flow network G=(V,E) is a partition of V into S and T=V-S such that s ∈ S and t ∈ T. If f is a flow, then the net flow across the cut(S,T) is defined to be f(S,T). The capacity of the cut (S,T) is c(S,T) A minimum cut of a network is a cut whose capacity is minimum over all cuts of the network

12/12 v1

11/16 s

8/13

v3 1/4

10

15/20

4/9 t

7/7 11/14 v2

v4

4/4

•The net flow across (S,T) is f(s,t)=19, and the capacity is c(S,T)=26 •The net flow across cut is f(v1,v3) + f(v2,v3) + f(v2,v4) = 12+(-4)+11= 19 •Capacity is c(v1,v3)+c(v2,v4) = 12 + 14 = 26

Ford-Fulkerson-Method(G,s,t) 1. 2. 3. 4.

Initialize flow f to 0 While there exists an augmenting path p Do augment flow f along p Return f

Ford Fulkerson algorithm 

The Ford Fulkerson method is iterative,



Starts with f(u,v) for (u,v) ∈ V, initial flow of value 0.



The method is based on the augmenting path which is defined as a path from s to t along which we can push more flow and then augment flow along this path.

Procedure Ford_Fulkerson_method(G,s,t):    

For each edge (u,v) ∈ E[G] do f[u,v]  0 f[v,u]  0 While there exists path p from s to t in residual network Gf



do cf(p)  min{ cf(u,v):(u,v) is in p}



for each edge (u,v) in p do f[u,v] f[u,v] + cf(p)

 

f[v,u] -f[u,v]



Running time for this algorithms is O(E * |f*|) where f* is the maximum flow found by algorithm.



First three Lines take time θ(E).



The while loop of last five lines is executed at most |f*| times, since the flow value increases by at least one unit in each iteration.

12 v1

16

4

10

s

13

v2

I/P Residual network

20

9 t

7

v3

4

v4 14

4/12 v1

4/16 Flow network

s

13

v2 4

10

20

4/9 t

7 4/14 v3

v4

4/4

8 v1

12 s

5

4

10

Residual network

20

4 4

13

v2

t

7

4 10 v3

4

v4 4

4/12

11/16 Flow network

s

13

v1

v2 4

7/10

7/20

4/9 t

7/7 11/14 v3

v4

4/4

8 v1

5 s

11

3

5 7

4

Residual network

13

4 11

13

v2

7

t

3 v3

4

v4 11

12/12 v1

11/16 Flow network

s

8/13

v2 1/4

10

15/20

4/9 t

7/7 11/14 v3

v4

4/4

12 v1

5 s

3

11

11

v2

8 5

5

5 7

4

Residual network

15

t

3 v3

4

v4 11

12/12 v1

11/16 Flow network

s

12/13

v2 1/4

10

19/20

9 t

7/7 11/14 v3

v4

4/4

Residual network

12

v1

5

3

11 11

s

v2

9 7

1 19

12 1

3 v3

v4 11

4

t

Max flow min cut theorem 

This theorem tell us that a flow is max. if and only if its residual network contains no augmenting path.

The orem s tat es that , If f is a flow in a flow network, G = (V,E) with the source and sink t then, the following conditions are equivalent: 5. F is a max. flow in G. 6. The residual network G1 contains no augments paths. 7. |F| = c(S,T) for some cut (S,T) of G.

Maximum Bipartite Matching 

Given an undirected graph G=(V,E), matching is a subset of edges M is subset of E such that for all vertices v ∈ V, at most one edge of M is incident on v.



We say that a vertex v ∈V is matched by matching M if some edge in M is incident on v; otherwise, v is unmatched.



A maximum matching is a matching of maximum cardinality, that is, a matching M such that for any matching M’, we have |M|>= |M’|.

A bipartite graph G=(V,E) with vertex partition V= L U R

A matching with Cardinality 2

A matching with Cardinality 3



We can solve the maximum match finding problem using flow networks.



Put source and sink on the graph such that source connects all the vertices on left side of the graph with single edge to each vertex and do the same for the sink. Now assign weight 1 to all the edges in the graph.



Run ford Fulkerson algorithm to find max flow.



Max. cardinality = Max flow