Algorithms Notes
.png)
Algorithm Basics
.png)
Divide And Conquer
.png)
Greedy Algorithm
.png)
Dynamic Programming
.png)
Shortest Path
.png)
Backtracking
.png)
Minimum Spanning Tree
.png)
Maximum Flow
.png)
Complexity Classes
Heading
Q
1
Explain Network Flow Problems

Ans
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 ∞
Figure shows a multiple sources and sinks flow network and an equivalent single source and sink flow network

Q
2
Explain Maximum Bipartite Matching

Ans
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' |.
