Algorithm Design Techniques
Due: Beginning of class, Tues Oct 16
Late assignments -10% per day, including
Please give late assignments to Perouz (T.A) in McConnell 232
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. Let G=(V,E) be a directed
graph. A vertex cover is a
subset S of vertices such that each edge in E has at least one endpoint in S. Eg. the
set V itself is a vertex cover, and remains a vertex cover if one
vertex is deleted. The size of the cover is the number of vertices in S.
(a) Show that the size of any matching (eg. number of matching edges)
in G is less than or equal to the size of any vertex cover in G. (Note
G may be non-bipartite.)
(b) Show how to find the minimum size vertex cover in a bipartite graph by using network
flows. (Hint: study the
optimum matching and the residual graph at termination). Prove the size
of a minimum vertex cover is the same as the size of a maximum matching.
Illustrate by constructing a graph with 6 vertices in each part, and a
maximum matching of size 5. Show the vertex cover.
2. Text p. 415, question 3 (a) (b). In each case show the maximum
flow and the minimum cut.
3. Suppose you have a network and
find its max flow f and minimum cut (A,B). Now you increase the
capacity of every edge by one. Is it still true that (A,B) gives a
minimum cut? Give a proof or counterexample.
4. Text p. 423 problem 16.