Heading

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

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