Scribd
Upload
80 views1 page

Graph Theory Assignment 2: S. No Question Prove or Answer The Flowing

This document contains 5 questions related to graph theory and algorithms for finding maximum flows in networks. The questions cover proving properties of matchings in bipartite graphs, restating the max-flow min-cut theorem, applying the Ford-Fulkerson and Edmonds-Karp algorithms to example graphs, relating maximum matchings to maximum flows, and analyzing the runtime of the Edmonds-Karp algorithm.

Uploaded by

Ashutosh Acharya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
80 views1 page

Graph Theory Assignment 2: S. No Question Prove or Answer The Flowing

This document contains 5 questions related to graph theory and algorithms for finding maximum flows in networks. The questions cover proving properties of matchings in bipartite graphs, restating the max-flow min-cut theorem, applying the Ford-Fulkerson and Edmonds-Karp algorithms to example graphs, relating maximum matchings to maximum flows, and analyzing the runtime of the Edmonds-Karp algorithm.

Uploaded by

Ashutosh Acharya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph Theory Assignment 2

S. No Question
Prove or Answer the flowing.

1 Let M be a matching in a bipartite graph G. Show that if M is sub-optimal, i.e. contains


fewer edges than some other matching in G, then G contains an augmenting path with
respect to M.

2 Given G, f, we define the bottleneck capacity of an s-t path as the least residual capacity
of its edges. Therefore, a path is an augmenting path iff it has non-negative bottleneck
capacity. We restate the max-flow min-cut theorem in the following alternate form:
1. There is an s-t cut S with C(S, Sc) = Val(f).
2. If is a max flow in G.
3. There is no augmenting path for f in G.

3 Find the max flow for the following graphs (shown Figures a & b) using Ford
Fulkerson Algorithm and Edmonds Karp Algorithm indicating all the internal steps:
augmenting paths, residual graphs and etc.

Figure (a) Figure (b)

4 Let G (A ∪ B, E) is a bipartite graph. Let (G’, s, t, c) be a flow networks constructed by


Construct Network on G:
1. The size of the maximum matching M of G equals the value of the maximum
flow f on G’.
2. ExtractMatching returns a maximum matching when given the max flow f on
G’.

5 Let D = (V, A) be a digraph, (S, T, b, c, d) a flow-quintuple for D. Let some (S, T, b, c,


d)-flow f be given. Then the Edmonds-Karp Algorithm, initiated with f, stops after at
most |V | · |A| iterations and yields a maximal flow.

END

You might also like