MS&E 217/317,
Combinatorial Optimization, Autumn
2003-04.Instructor: Ashish Goel
Handout 9
HW3. Given 11/15/2003, Due
11/26/2003, in class, or in my office (by 11am).
No collaboration allowed.
The programming exercise can be submitted as
late as 12/5/2003. This HW has double weight.
1.
Implement the
flow-augmentation procedure of the Edmond-Karp algorithm. Assume that the
current flow x is given to your, and you have to find the path to augment on as
well as the amount of flow to send (i.e. the width of the augmentation). Submit
your code by email. Please do not use fancy libraries, user-defined .h files
etc. – put your code in a single file. C, C++, Pascal, Basic, Lisp, Fortran,
Java are all acceptable. Please do not use any graphics etc – it would be nice
if your code compiles and runs on Unix machines.
Assume the following input format:
First line: n
Second line:
m
Next m lines:
v_j w_j x_j u_j
Here n is the number of vertices, m is the number of edges,
v_j, w_j are the endpoints of the j-th edge, x_j is the current flow on the
j-th edge, and u_j is its capacity. Assume that vertex 1 is the source and
vertex n is the destination. Your output must list all the vertices of the path
you do the augmentation on, followed by the width of the augmentation,
everything on a different line. I will do automated testing, so please adhere
to this format strictly. Assume that the input comes from stdin (i.e. the user
types it – make sure you are using scanf or cin if you use C/C++). If the input
is
8
9
1 2
0 1
2 3
0 1
3 4
0 1
4 8
1 1
1 5
1 1
5 4
1 1
5 6
0 1
6 7
0 1
7 8
0 1
then the output must be the following:
1
2
3
4
5
6
7
8
1
2.
The following theorem is a
classical result due to König. Prove it using the max-flow min-cut theorem. A
vertex cover of a graph is a set of vertices such that each edge has at least
one endpoint in the graph.
König’s Theorem: The size of the largest matching in an
undirected bipartite graph is the same as the size of the smallest vertex
cover.
3.
The following theorem is a
classical result due to Hall. Prove it using the max-flow min-cut theorem.
Hall’s Marriage Theorem:
Suppose we are given N men and N women. Each man p has a compatibility set Sp
of women that he can be married to. Then there exists a perfect matching
(i.e. a way to marry each man to a unique woman) iff for any K men, the union
of their compatibility sets is of size at least K.
4.
Prove that the total number
of augmentations that can be done by the Edmond-Karp algorithm is at most nm/2.
5.
Problem 3.4 from the text.
6.
Problem 3.7 from the text.
7.
Problem 3.10 from the text.
8.
Problem 3.14 from the text. Hint:
Think Dijkstra.
9.
Problem 3.33 from the text.
10. Problem 3.35 from the text.
11. Problem 4.3 from the text.
MS&E 217: Do problems 1, 2, 4, 5, 7, 8, 10, and 11. Problem 1 is
worth 50 pts, and all other problems are 10 pts.
MS&E 317: Do problems 1, 2, 3, 5, 6, 9, 10, and 11. Problem 1 is
worth 50 pts, and all other problems are 10 pts. If you did the two matroid
problems, you can omit any one 10 pt problem.
MS&E 317 students: The lectures on combinatorial optimization
problems in game theory will not be a part of either the HWs or the final.