Maximum Flow: Algorithm Class Notes

Updated: Aug 18

Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.

  1. Algorithm Basics

  2. Divide And Conquer

  3. Greedy Algorithm

  4. Dynamic Programming

  5. Shortest Path

  6. Backtracking

  7. Minimum Spanning Tree

  8. Maximum Flow

  9. Complexity Classes

Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.

  1. Explain Network Flow Problems.

  2. Explain Maximum Bipartite Matching.


Maximum Flow


Question- 1) Explain Network Flow Problems.

Answer: The most obvious flow network problem is the following:


Problem1: Given a flow network G = (V, E), the maximum flow problem is to find a flow with maximum value.


Problem 2: The multiple source and sink maximum flow problem is similar to the maximum flow problem, except there is a set {s1,s2,s3.......sn} of sources and a set {t1,t2,t3..........tn} of sinks.


Fortunately, this problem is no solid than regular maximum flow. Given multiple sources and sink flow network G, we define a new flow network G' by adding


A super source s,

A super sink t,

For each si, add edge (s, si) with capacity ∞, and

For each ti,add edge (ti,t) with capacity ∞


 

Question- 2) Explain Maximum Bipartite Matching.

Answer: A Bipartite Graph is a graph whose vertices can be divided into two independent sets L and R such that every edge (u, v) either connect a vertex from L to R or a vertex from R to L. In other words, for every edge (u, v) either u ∈ L and v ∈ L. We can also say that no edge exists that connect vertices of the same set.

Maximum Bipartite Matching


Matching is a Bipartite Graph is a set of edges chosen in such a way that no two edges share an endpoint. Given an undirected Graph G = (V, E), a Matching is a subset of edge M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v.


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


 



10 views0 comments

Recent Posts

See All