MA010 Tutorial 4
Frederic Dupuis This tutorial covers material from lectures 4 and 5.
Problem 1
In class, it was claimed that it can make a big difference to look for the shortest augmenting path when running the Ford-Fulkerson algorithm for finding the maximum flow. Here we will see what can happen when we don't do this. Consider the following graph:
where X » 1 is some very big number, and tp = ^(V5 — 1) as 0.618034, chosen so that 1 — ip = ip2. Consider also the following augmenting paths:
A B C D
(a) Suppose we run the Edmonds-Karp algorithm on this graph (i.e. by always taking shortest augmenting paths). What is the resulting maximum flow? What is the corresponding minimum cut?
(b) Suppose instead that we start by taking path D. What are the residual capacities of the three horizontal edges?
(c) Now, suppose that the residual capacities of the three horizontal edges are tpk~1, 0, ipk, and that we take augmenting paths B,C,B,A (in that order). What are the residual capacities at the end? How much flow was added by taking these four steps?
(Remember that 1 — <p = <p2!)
1
(d) Suppose we take path D, then paths B,C, B, An times. What is the total flow? How long will it take to reach a maximum flow by making this choice of augmenting paths?
Source: http: //web. engr .Illinois . edu/ ~ je ffe/'teaching/'algorithms /notes /'2 3-max flow.
pdf
Problem 2
Use the Edmonds-Karp algorithm to find a maximal matching in the following bipartite graph:
What is the minimum cut found by the algorithm? Give a minimum vertex cover corresponding to this cut.
Problem 3
A line in a matrix is a row or a column. Show that the minimum number of lines covering all nonzero entries of the matrix is equal to the largest number of nonzero entries such that no pair of them lie on a common line.
Source: www. ams. jhu. edu/'-abasu9/AMS_550-4 72-672/HW-4 .pdf
Problem 4
A maximum independent set is a set of vertices such that no two of them are joined by an edge. A covering of vertices by edges is a set of edges such that every vertex is an endpoint of at least one of these edges. Prove that if G is a bipartite graph with every vertex having degree at least 1, then the size of the largest independent set is equal to the size of the smallest covering of vertices by edges.
Hint: Think of the relationship with Konig's theorem (i.e. max matching = min vertex cover in bipartite graphs). What is the complement of a vertex cover?
Source: http: //www.ms. uky. edu/~lee/ma515fa09/hw6.pdf
2