Scribd
Upload
21 views14 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.

Uploaded by

Deepa R
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
21 views14 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.

Uploaded by

Deepa R
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
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 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

You might also like