0 ratings 0% found this document useful (0 votes) 62 views 14 pages Maximum Flow Problem
The document discusses the simplex method and the Ford-Fulkerson algorithm for solving linear programming and maximum flow problems, respectively. It outlines the steps involved in the simplex method, including forming the next tableau and checking for feasibility, as well as the concepts of capacity constraints, augmenting paths, and cuts in flow networks. Additionally, it provides examples and explanations of how to compute maximum flow using these algorithms.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here .
Available Formats
Download as PDF or read online on Scribd
Go to previous items Go to next items
Save Maximum Flow Problem For Later
gn and Analysis of Algorithms 4-15 erative Improvement
‘ep 4: Forming the next tableau : Divide all the entries in the pivot row by its entry
a pivot column. Subtract from each of the other rows, including the objective row,
the new pivot row multiplied by the entry in the pivot column of the row in question.
this will make all the entries in the pivot column 0's except for 1 in the pivot row.
geplace the label of the pivot row by the variable's name of the pivot column and go
ack to Step 1.
fos
1. Write the procedure to initialize simplex which determines if a linear program is feasible or not.
Summarize the simplex method.
Describe in detail the simplex algorithm methods.
List the steps in simplex method and give the efficiency of the same.
Give the summary of the simplex method.
What is iterative improvement? Elaborate the steps in the simplex method with an example.
AU : Dec 19, Marks 13
EE] the Maximum Flow Problem AU : May-15,16,19, Dec.-15,16, Marks 13
Maximum flow is a maximum feasible flow between source and sink. Here the word
flow means the rate at which the material moves through underlying object. But when
the material moves through some object it is very much essential to consider its
“pacity. In maximum flow problem, we want to compute the greatest rate at which
Sslerial can be moved or traveled from source to sink without violeting any capacity
0. If (u,v) ¢ E then (uv) = 0.
There are two distinguishing nodes in flow network called source and sink through
ch the material moves. That means a flow is from source to sink. There are three
"Portant properties of flow networks.
1 Capacity Constraint : For all u,v € V the flow of edge (u,v) is always less than or
qual to the capacity of that edge (u,v). ie. f(u,v) < (uv)
TECHNICAL PUBLICATIONS® - an up-thrist for knowledge —
Horative Improvement
Design and Analyala of Algorithi
iS ret
2. Skew Symmetry : For all u, ve vf (u,v) == FC vet) that a vere edge,
3. Flow Conservation : For any vertex v except s,t Le, source and sink respectively,
Yu, = 0
‘The Value of flow from ut to v can be defined as
I= Die,w
vev
For example
Fig, 4.3.2 Flow notwork In which edge (u,v) Is tabolod t(u,vife(u,v)
TECHNICAL PUDLICATIONS® « an upttuust for knowledge in ‘and Analysis of Algorithms 4-17 Iterative Improvement
Note th
“derlying networ
at in Fig. 43.2 f(uv) represents flow and c(u,v) represents capacity of
k. The flow is never exceeded than capacity.
ol The Ford-Fulkerson Method
This algorithm works for solving maximum-flow problem. This is an_ iterative
sethod. The Ford-Fulkerson algorithm makes use of 3 important things
» Residual network
«+ Agumenting path
© Cuts.
Let us discuss them along with some example before through actual method.
1. Residual Network
Suppose we have a flow network G = (V, E) with source s and sink t. Let every edge
uy is having a pair flow/capacity then representation of a graph with residual capacity is
dled residual network.
c(uv) = clu,v) - f(u,v)
For example
Fig. 4.3.3 Graph G
2 The Augmenting Path
An augmenting path is a simple path p from s to t in residual network Gy. This is the
Path which never violates the capacity constraints.
enusunal BURL ICATIONS® « an up-thrust for knowledge ant Rrerative lmorovement
Desor ant trays of Agents
For ewmple
Fig. 4.3.5 Augmenting path
The graph is in maximum flow if there is no augmenting path.
3. Cuts in Flow Networks
Cut is a collection of ares such that if they are removed there is no path from s to t
TECHNICAL PUBLICATIONS® - an up-thrust for knowledge wy ysis of Algorithms 4-19
ete Iterative Improvement
yor example
| Fig. 4.3.6 Cut
Accut is said to be minimum in a network whose capacity is minimum over all cuts
of the network.
Ford-Fulkerson Method
let us understand this method along with an example. Let us first look at the
algorithm.
f e %
Mend of algorithm Sees
Erample : Let us first find the augmenting path.
Step 4;
na augmenting path is marked by thick
flys, is a path which gives maximum
N '
a Wwe will find the residual capacity
“ i Gu question that arises here is that
fing ° find residual capacity? Well, just
a minimum value along the
TECHNICAL PUBLICATIONS® > an up-thrust for knowledge Step 3:
Iterative ir
Design and Analysis of Algorithms 4-20 i improvement
residual path, Here now it is 4. ie. c(2, t). Now we will design a residual graph py
considering residual capacity 4,
We will apply while loop of above given algorithm.
Step 2: Here along the augmenting path the residual capacity is c(3,t) = 5 Hence we
can draw residual network.
Residual graph
Graph with augmenting path [Maximum flow = 4 + 5 =9|
Now we will again mark augmenting path for maximum flow.
(By refering graph in step 1)
TECHNICAL PUBLICATIONS® - an up-hrust for knowledge =
Analysis of Algorithms
op
erative Improvement
pore p= ¢ (2/3) =3
{Maximum flow =44+54+3=12
| “Fence the residual graph is as follows :
Jhis is the residual graph, we will now
fad the augmenting path — giving
| jaximum flow from source to sink. Here
te only remaining path is s-1-4-t.
| The = (81) = 2.
«Maximum flow = 4 +5+3+2=14
Step 5: Now there is no path from s to t in following graph, hence we will exit the
“hile loop with maximum flow = 14.
Now once again consider the original graph which we have taken for discussing
“Pove example.
TECHNICAL PUBLICATIONS® = an up-thrust for knowledge Design and Analysis of Algorithms 4-22 Mterative Improvement
Here the cut is shown by
dotted line
Hence
cut = ((8,3),(s,2),(8,1)}
When the graph has maximum flow then it gives minimum cut which is as shown
below.
GEEREEED) How do you compute a maximum flow for the following graph using
Ford-Fulkerson method ?
Solution :
Step 1; As there is no sink node 't' is mentioned we will create a sink node with eq"
distances from ‘v' and 'y’. The graph will then be
TECHNICAL PUBLICATIONS® - an up-thrust for knowledge y
Analysis of Algor
yo and —
4-23 ftorative Improvement
gy 2 We will find augenented path andl revidual enpaclty.
the path marked by a thick line, ‘The residual capacity is minimum value i.e. 1.
lence residual graph will become.
Sep 3: As the path from u to v is 0, we consider that there is no path between u and v.
Now we will find another path.
ae
TECHNICAL PUBLICATIONS” = an up-thrust for knowledge Iterative Improvem
Design and Analysis of Algorithms 4-24 ent
4; As the path from u to x and x to y is 0 we consider that there is no path
Step 4+ 1 cweenva and x and between x and y. Now we will find another path.
Step 5:
<. Maximum flow =3+5=8
Step 6 : As path from s to x is 0, there is no path between s and x.
TECHNICAL PUBLICATIONS® - an up-thrust for knowiodge par Anais of Algorithms 4-25 Htorative Improvement
as there is no augmented path possible the maximum flow is 8,
the residual graph becomes.
GEERIZED) Determine the max-flow in the following network. XC ESUS TATE
7 4
Solution :
Step 14: We will mark augmenting path by thick line, this is a path which gives
maximum flow.
3, Re minimum value along the path is
Hence residual capacity is 3.
TECHNICAL PUBLICATIONS® - an up-thrust for knowledge iterative Improvement
-26
Design and Analysis of Algorithms 2 4
Hence
#' The minimum value
along this path is 2
TECHNICAL PUBLICATIONS® - an up-thrust for knowledge jis of Algorithins
ns Analy
pS er
Morattve Improvement
Maximum flow = 3+2 = 5
tup 3: The only path remaining from source to sink ¢ is #-1-3-. The minimum value
along, thin path is 1.
‘Maximum flow = 3+2+1 = 6
Aw there Is no path from source # to sink t, hence we will stop finding residual path
Ong
‘I we obtain. maximum flow as 6.
ere —xy
Iterative i
Dasign and Analysie of Algorithms 4-26 Improvemery
Analysis + The algorithm for Ford-Fulkerson has a while loop which executes for
O(F). Hence running time of Ford-Pulkerson algorithm is O(EF*) Where F* i, the
maximum flow found by algorithm,
Bm Cn)
1. Explain Max-flow problem,
2. State and prove Max-Flow Min-Cut theorem. AU : May-16, Dec.-16, Marks 8
eR
Maximum Matching in Bipartite Graphs
eee
Many times we have to pair the vertices from two sets, For example - If there are m
applicants for the jobs and there are n jobs. Then each applicant must be paired with
some job. It is easy to represent the clements of such problems using graph using the
edges between the vertices of two distinct Sets. Before understanding the maximum
matching, bipartite graph problem, let us understand some of the terms used within it.
Bipartite Graph : The graph G =(V,E) in which the vertex set V is divided into tw
disjoint sets X and Y in such a way that every edge e © E has one end point in X and
other end point in Y,
For example
1
A
2
8
. 3
o 4
E
ts Y
Fig. 4.4.4 Bi-partite graph
Matching + A matching mj 8 subset of ea
Met Of edges
ant
i ears i
mot one edge in M. In oy such that cach node in V apP!
0
ther w ane that *
two edges share a vertex Orde matching, in a graph je a subset of edge
Two-colorable Graph +, tie
1 BPH CaN be cotrrd scute P seve fi
colorable graph) such thas
