Scribd
Upload
13 views9 pages

Capacitated Network Flow Concepts

The document defines key terms related to flows and connectivity in capacitated networks including source/sink vertices, cuts, maximum flow, and augmenting paths. It presents several theorems including that maximum flow equals minimum cut capacity and that a flow is maximum if and only if there are no augmenting paths. The Edmonds-Karp algorithm for finding maximum flow is also described.

Uploaded by

saswatashu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views9 pages

Capacitated Network Flow Concepts

The document defines key terms related to flows and connectivity in capacitated networks including source/sink vertices, cuts, maximum flow, and augmenting paths. It presents several theorems including that maximum flow equals minimum cut capacity and that a flow is maximum if and only if there are no augmenting paths. The Edmonds-Karp algorithm for finding maximum flow is also described.

Uploaded by

saswatashu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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.

Common questions

Powered by AI

The maximum flow in a capacitated network is directly related to the capacity of the minimum cut, as stated in the Max-Flow Min-Cut Theorem . This relationship is important because it establishes that the maximum amount of flow that can be sent from the source to the sink is exactly equal to the capacity of the smallest possible cut separating the source and sink. This gives a dual perspective on the flow problem, helping to verify flow maximality and effectively solve optimization problems .

A capacitated network is defined as a weighted directed graph with an integer valued function, known as the capacity function, applied to its set of arcs or edges . This network is significant in flow problems because it accommodates the determination and management of flows from a source to a sink, constrained by the capacities of the arcs. These capacities influence the maximum feasible flow that can be achieved, making them critical in optimization problems in network theory .

The concept of a mincut complements the idea of maximum flow by establishing that the capacity of the smallest cut across the network equals the maximum flow that can be achieved. This relationship underpins the duality principle in network flow optimization, where solving for one provides insight into the other . The mincut represents the bottleneck for the flow, serving as the limiting factor for the maximum achievable flow between the source and the sink, thus highlighting potential areas for network capacity improvement .

An f-augmenting path is a path from the source to the sink in which no forward edge is f-saturated and no backward edge is f-free . If such a path exists, it indicates the current flow is not maximal. The effect of an f-augmenting path is that it allows the increase of flow by the excess flow capacity of the path, ensuring that the flow along the path can be increased in forward arcs and decreased in backward arcs to enhance the overall flow from the source to the sink .

The Ford-Fulkerson algorithm is important for solving the maximum flow problem because it provides a systematic method to find augmenting paths in a network and increase flow iteratively until no further augmenting paths exist. By doing so, it guarantees that the flow has reached its maximum possible value . Additionally, it aligns with the Max-Flow Min-Cut Theorem by confirming that the maximum flow equals the minimum cut capacity, thus supporting the theoretical framework of network flow problems .

Intermediate vertices in a network are crucial for defining feasible flows. For a flow to be feasible, at every intermediate vertex, the inflow (sum of flows into the vertex) must equal the outflow (sum of flows out of the vertex). This balance ensures that flow conservation is maintained throughout the network, except at the source and sink vertices . This principle essentially governs the continuity of flows in and out of vertices in network models .

Theorem-4, known as the Max-Flow Min-Cut Theorem, implies that the maximum flow achievable in a network corresponds exactly to the capacity of the minimum cut separating the source and sink. This has profound implications for network flow optimization as it provides not just a method to verify maximum flow values but also assists in identifying the critical constraints or bottlenecks (min-cuts) that define the limit on flow. This dual perspective enables both validation and strategic planning for capacity enhancement in network design .

Flow through a network can be increased using flow augmenting paths by exploiting paths where forward edges are not saturated and backward edges are not at full capacity (f-free). By identifying such paths, the flow can be augmented by increasing the flow along forward edges and decreasing along backward edges by the minimum unused capacity in the path—a process known as augmenting the path. Repeating this process until no more augmenting paths are found results in achieving maximum flow .

According to Theorem 3, a flow is considered a maximum flow if and only if there is no f-augmenting path in the network. In practical terms, this means all potential paths for increasing flow have been exhausted, and the current flow is equal to the capacity of any possible cut in the network. The absence of f-augmenting paths ensures that the flow has been maximized according to the constraints posed by the network capacities .

The Edmonds-Karp Algorithm utilizes a series of breadth-first searches (BFS) to improve the flow in a network. The process involves constructing a digraph D(f) based on the current flow, detecting augmenting paths using BFS from the source to the sink, and then enhancing flow along these paths incrementally. This iterative process continues until no more augmenting paths can be found, at which point the maximum flow value is determined as the outflow from the source. This algorithm ensures that each iteration is efficiently processed, making it suitable for optimizing flows in networks .

You might also like