Flows and Connectivity

FLOWS AND CONNECTIVITY
SOME DEFINITIONS
 CAPACITATED NETWORK: A weighted directed graph with an integer

valued function c known as capacity function defined on its set of
arcs/edges is called a capacitated network.
 SOURCE VERTEX : A special vertex s with in-degree 0 is designated as
the source vertex
 DESTINATION VERTEX/SINK : A special vertex t with out-degree 0 is
designated as the destination vertex/sink
 All vertices other than the source vertex or the destination vertex are
INTERMEDIATE vertices
 Let c(e) be the cost of the edge e(u,v) is called the capacity of e. The
capacity of an edge is greater than 0
 A flow f in a network is an integer valued function defined on its set of
arcs such that 0 ≤ f(e) ≤ c(e) for each arc e.
 The sum of flows along all the arcs directed to the vertex i is the inflow
into i
 The sum of flows along all the arcs directed from the vertex i is the
outflow from i
 A flow is a feasible flow if it satisfies the feasible condition: For every
intermediate vertex (i.e. vertex other than source or sink) i, the inflow
into i is equal to the outflow from i.
 A feasible flow in a capacitated network such that the value of the flow
is as large as possible is called the maximum flow in the network.
 The problem of finding a feasible flow in a capacitated network such that
the value of the flow is maximum is known as maximum flow network.
 It is assumed that the digraph is asymmetric.
CUTS IN CAPACITATED NETWORK
Any partition of vertex set V in the weighted digraph G=(V,E) into two sets
S and T such that the source s is in S and sink t is in T and the set
(S,T)={(u,v)|u є S and v є T and (u,v) є E)} is called a cut or source-sink-cut in
the network since no flow can be sent from source to sink if all the arcs in
the cut are deleted.
A cut is called a mincut if its capacity does not exceed the capacity of any
other cut.
If f is a feasible flow in the network the sum of flows along the arcs in the
cut (S,T ) is the flow f(S,T) along the cut. Obviously, 0 ≤ f(S,T) ≤ c(S,T)
THEOREM-1 :If f is any feasible flow in the capacitated network G and if

(S,T) is any cut in the network, f(G)=f(S,T)-f(T,S)
PROOF
The vertex set V={1, 2, ………, n}.
S is any set of vertices that contains vertex 1 (source) and T is its

complement that contains the vertex n (the sink)
∑jf(i,j) - ∑jf(j,i) =f(G) when i=1
So, ∑i є S∑j f(i,j) - ∑i є S∑j f(j,i) =f(G). If i and j are both in S, the term
f(i,j) appears in first summation ∑i є S∑j f(i,j) as well as in the second
summation ∑i є S∑j f(j,i) .
So it is enough if we let the subscript j vary for all j in T
Hence, ∑i є S∑jєT f(i,j) - ∑i є S∑ jєT f(j,i) =f(G).

 COROLLARY-1 : The value of f(G) of any feasible flow f in a network is
also equal to the inflow to the sink
 COROLLARY-2 :If f is any feasible flow and if (S,T) is any cut, f(G) ≤
c(S,T)
If f is a feasible flow in a capacitated network the arc(i,j) is
 f-saturated if f(i,j) = c(i,j).

 f-zero or f-free if f(i,j) = 0
 f-positive if 0 < f(i,j) < c(i,j).
THEOREM-2:
a) If f is a feasible flow and if (S,T) is any cut, f(G) = c(S,T) if and

only if every arc in (S,T) is f-saturated and if every arc in the cut
(T,S) is f-zero.
b) If f is a feasible flow and if (S,T) is any cut such that f(G) =
c(S,T), f is the maximum flow and (S,T) is the minimum cut.
PROOF
a)f(G) = c(S,T) if and only if f(S,T) – f(T,S) =c(S,T). This is possible if and only
if every arc in cut (T,S) is f-zero and every arc in cut (S,T) is f-
saturated.
b)Let f’ be a maximum flow and (S’,T’) be a minimum cut in the network.

Then f(G) ≤ f’(G) ≤ c(S’,T’) ≤ c(S,T)
Now if f(G)=c(S,T), then it implies that f(G) = f’(G) = c(S’,T’) = c(S,T)
So, f is indeed a maximum flow and C(S,T) is a minimum cut
FLOW AUGMENTING PATH
 An alternating sequence P of vertices and arcs of the form v0, e1, v1, e2,
……….. , ek, vk, in which no vertex is repeated is called a semipath from v0
to vk.
 Arc ei in this path is a forward edge if it is directed to vi . Otherwise it is
a backward edge in P.
 A semipath P is said to be f-unsaturated if no forward path is f-
saturated and no backward edge is f-free
 An f-unsaturated path is path from source to sink is called an f-
augmenting path.
 For each arc ei in an f-augmenting path P, δ(ei) is defined as c(ei)-f(ei) if ei
is a forward arc and f(ei) if ei is a backward arc.
 The excess flow capacity of a semipath P is δ(P) = min {δ(ei) : ei є P}
If P is an f-augmenting path with excess flow capacity δ(P), a new feasible flow
f’ can be obtained by increasing the flow of each forward edge by δ(P), and
decreasing the flow along each backward edge by δ(P) such that f’(G)=f(G) +
δ(P). Once this is accomplished, the semipath is no longer an f-augmenting path.
In other words if there is an f-augmenting path in a network, flow f is not a
maximum flow as its flow value can be increased using this augmenting path. It
turns out the converse of this assertion is also true.
In the semipath given in FIGURE-4 the flow can be increased by increasing the
flow along forward arcs by 1 unit and decreasing the flow along backward arc by
1 unit as shown in FIGURE-5
THEOREM-3
A flow f in a capacitated network is a maximum flow if and only if there is

no f-augmenting path in the network.
PROOF
We need to show that if there are no f-augmenting path with respect to f, f is
indeed a maximum flow.
Let S be the set of all vertices i such that there is an f-unsaturated path from
the source vertex 1 in S to i.
Obviously 1 is a vertex in S and the sink (vertex n) is not in S.
Thus there is a cut (S,T) in the network.
Let <i,j> be any arc inn this cut.
Since there are no f-unsaturated path from source to j, arc <i,j> is necessarily
saturated.
Likewise any arc in (T,S) is f-zero
So the current flow value is equal to the capacity of cut (S,T). Hence the
current flow is maximum.
THEOREM-4(FORD-FULKERSON THEOREM)
In a capacitated network, the value of maximum flow is equal to the
capacity of the minimum cut. This theorem is also known as MAX-FLOW-
MIN-CUT THEOREM
PROOF
Let f be a maximum flow
Let S be the set of vertices i such that there is a f-unsaturated path from the
source to i.
Then the complement T of S is non-empty.
Thus there is a cut (S,T)
Each arc in this cut is f-saturated and each arc in the cut in (T,S) is f-zero.
So the flow value f(G) is equal to c(S,T) which is a minimum cut.
THE EDMONDS-KARP ALGORITHM to solve the maxflow problem
INPUT:
 A capacitated network with a capacity function c and an initial flow f .

 A vertex set V= {1,2,…………..,n] where 1 is the source vertex and n is the
sink.
 Capacity of arc > 0
Step1: Construct a digraph D(f) =(V,E’) as follows:
(a) If (i,j) is an f-saturated arc in E, (j,i) is an arc in E’

(b) If (i,j) is an f-zero arc in E, (i,j) is an arc in E’
(c) If (i,j) is an f-positive arc in E, both (i,j) and (j,i) are in E’
Step2: Starting from the source vertex apply a breadth first search (BFS)
algorithm in D(f) to obtain a directed path from source to sink. If there is no
such path, go to step 4
Step3: The directed path in the digraph D(f) from the source to sink n
obtained in step-2 is a semipath in G with positive excess flow capacity, so it is
an f-augmenting path. Increase the flow value in the network by using this path.
Go to step 1
Step4: The maximum flow value is the outflow from the source. Let S be
the set of vertices that can be reached from vertex 1 in D(f) and let T be its
complement. (S,T) is the minimum cut.

Flows and Connectivity

Uploaded by

Copyright:

Available Formats

Flows and Connectivity

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Flows and Connectivity

Uploaded by

Copyright:

Available Formats

FLOWS AND CONNECTIVITY

 CAPACITATED NETWORK: A weighted directed graph with an integer

THEOREM-1 :If f is any feasible flow in the capacitated network G and if

The vertex set V={1, 2, ………, n}.

S is any set of vertices that contains vertex 1 (source) and T is its

∑jf(i,j) - ∑jf(j,i) =f(G) when i=1

So it is enough if we let the subscript j vary for all j in T

Hence, ∑i є S∑jєT f(i,j) - ∑i є S∑ jєT f(j,i) =f(G).

If f is a feasible flow in a capacitated network the arc(i,j) is

 f-saturated if f(i,j) = c(i,j).

a) If f is a feasible flow and if (S,T) is any cut, f(G) = c(S,T) if and

b)Let f’ be a maximum flow and (S’,T’) be a minimum cut in the network.

FLOW AUGMENTING PATH

A flow f in a capacitated network is a maximum flow if and only if there is

THE EDMONDS-KARP ALGORITHM to solve the maxflow problem

 A capacitated network with a capacity function c and an initial flow f .

Step1: Construct a digraph D(f) =(V,E’) as follows:

(a) If (i,j) is an f-saturated arc in E, (j,i) is an arc in E’

You might also like