CS270 Homework 8 Solution

 1.(10pts) The following graph G has labeled nodes and edges between it. Each edge is labeled with its capacity.
(a) Draw the final residual graph Gf using the Ford-Fulkerson algorithm corresponding to the max flow. Please do NOT show all intermediate steps.
(b) What is the max-flow value?

2. (15pts) Determine if the following statements are true or false. For each statement, briefly explain your reasoning.
(a) In a flow network, the value of flow from S to T can be higher than the maximum number of edge disjoint paths from S to T. (Edge disjoint paths are paths that do not share any edge)
(b) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive flow.
(c) If you have non-integer edge capacities, then you cannot have an integer max flow.
(d) Suppose the maximum s-t flow of a graph has value f. Now we increase the
1
capacity of every edge by 1 . Then the maximum s-t flow in this modified graph will have a value of at most f + 1.
(e) If all edges are multiplied by a positive number k, then the min-cut remains unchanged.
3. (15pts) You are given a flow network with unit-capacity edges. It consists of a directed graph G = (V,E) with source s and sink t, and ce = 1 for every edge e. You are also given a positive integer parameter k. The goal is delete k edges so as to reduce the maximum s-t flow in G by as much as possible. In other words, you should find a subset of edges F ⊆ E such that |F| = k and the maximum s-t flow in the graph G′ = (V,EF) is as small as possible. Give a polynomial-time algorithm to solve this problem and briefly explain its correctness.
Follow up: If the edges have more than unit capacity, will your algorithm produce the smallest possible max-flow value?
4. (20 pts)A tourist group needs to convert their USD into various international currencies. There are n tourists t1,t2,...,tn and m currencies c1,c2,...,cm. Each tourist ti has Fi Dollars to convert. For each currency cj, the bank can convert at most Bj Dollars to cj. Tourist ti is willing to trade as much as Sij of his Dollars for currency cj. (For example, a tourist with 1000 dollars might be willing to convert up to 200 of his USD for Indian Rupees, up to 500 of his USD for Japanese Yen, and up to 300 of his USD for Euros). Assume that all tourists give their requests to the bank at the same time.
(a) Design an algorithm that the bank can use to satisfy all the requests (if it is possible). To do this, construct and draw a network flow graph, with appropriate source and sink nodes, and edge capacities.
(b) Prove your algorithm is correct by making a claim and proving it in both directions.
5. (15 pts) You have successfully computed a maximum s − t flow f for a network G = (V ;E) with integer edge capacities. Your boss now gives you another network G′ that is identical to G except that the capacity of exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was changed. Describe how you can compute a maximum flow for G′ in O(|V| + |E|) time.
2