Starting from:
$24.99
CSCI570 Homework 8 Solution
Spring2024
Q1. Determine if the following statements are true or false. If true, give a brief explanation. If false give a counterexample. (10 points)
(a) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive flow.
(b) If you have non-integer edge capacities, then you cannot have an integer max-flow value.
(c) Suppose the maximum s-t flow of a graph has value f. Now we increase the 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.
(d) If all edge capacities are multiplied by a positive number k , then the min-cut remains unchanged.
Q2. A tourist group needs to convert all of their USD into various international currencies.There are n tourists t1,t2, ...,tn and m currencies c1,c2, ...,cm. Each tourist tk has Fk Dollars to convert. For each currency cj , the bank can convert at most Bj Dollars to cj.Tourist tk is willing to trade at most Skj of their Dollars for currency cj. (For example, a tourist with 1000 dollars might be willing to convert up to 300 of their USD for Rupees, up to 500 of their USD for Japanese Yen, and up to 400 of their USD for Euros). Assume that all tourists give their requests to the bank at the same time. Design an algorithm that the bank can use to determine whether all requests can be satisfied. To do this, construct and draw a network flow graph, with appropriate source and sink nodes, and edge capacities.
Prove your algorithm is correct by making an if-and-only-if claim (10 points)
Q4. You are given a directed graph which after a few iterations of Ford-Fulkerson has the following flow. The labeling of edges indicate flow/capacity: (15 points)
a) Draw the corresponding residual graph.
b) Is this a max flow? If yes, indicate why. If no, find max flow.
c) What is the min-cut?
Q5. USC has resumed in-person education after a one-year break, with k on-site courses available this term, labeled c1 through ck. Additionally, there are n students, labeled s1 to sn, attending these k courses. It's possible for a student to attend multiple on-site courses, and each course will have a variety of students enrolled. (20 points)
(b) Assuming a viable solution is found for part (a) where each student is enrolled in exactly m courses, there arises a need for a student representative for each course from among the enrolled students. However, any single student can represent at most r (where r is less than m) courses in which they are enrolled. Develop an algorithm to check whether it is possible to appoint such representatives, building on the solution from part (a) as a foundation. Prove your algorithm is correct by making an if-and-only-if claim.
Q6. Given the below graph solve the below questions using scaled version of Ford-Fulkerson. (15 points)
a) Give the Δ and path selected at each iteration.
b) Draw the final network graph and the residual graph c) Find the maxflow and mincut
Q7:The following graph G has labeled nodes and edges between them. Each edge is labeled with its capacity. (10 points)
(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?
(c) What is the min-cut?
Q8. You are provided with a flow network where each edge has a capacity of one. This network is represented by a directed graph G = (V, E), including a source node s and a target node t. Additionally, you are given a positive integer k. The objective is to remove k edges to achieve the greatest possible reduction in the maximum flow from s to t in G. Your task is to identify a subset of edges F within E, where the size of F equals k, and removing these edges from G results in a new graph G' = (V, E-F) where the maximum flow from s to t is minimized. Propose a polynomial-time strategy to address this issue.
Furthermore, consider if the capacities of the edges are greater than one, and discuss whether your strategy still ensures the lowest possible maximum flow. (20 points)
Q1. Determine if the following statements are true or false. If true, give a brief explanation. If false give a counterexample. (10 points)
(a) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive flow.
(b) If you have non-integer edge capacities, then you cannot have an integer max-flow value.
(c) Suppose the maximum s-t flow of a graph has value f. Now we increase the 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.
(d) If all edge capacities are multiplied by a positive number k , then the min-cut remains unchanged.
Q2. A tourist group needs to convert all of their USD into various international currencies.There are n tourists t1,t2, ...,tn and m currencies c1,c2, ...,cm. Each tourist tk has Fk Dollars to convert. For each currency cj , the bank can convert at most Bj Dollars to cj.Tourist tk is willing to trade at most Skj of their Dollars for currency cj. (For example, a tourist with 1000 dollars might be willing to convert up to 300 of their USD for Rupees, up to 500 of their USD for Japanese Yen, and up to 400 of their USD for Euros). Assume that all tourists give their requests to the bank at the same time. Design an algorithm that the bank can use to determine whether all requests can be satisfied. To do this, construct and draw a network flow graph, with appropriate source and sink nodes, and edge capacities.
Prove your algorithm is correct by making an if-and-only-if claim (10 points)
Q4. You are given a directed graph which after a few iterations of Ford-Fulkerson has the following flow. The labeling of edges indicate flow/capacity: (15 points)
a) Draw the corresponding residual graph.
b) Is this a max flow? If yes, indicate why. If no, find max flow.
c) What is the min-cut?
Q5. USC has resumed in-person education after a one-year break, with k on-site courses available this term, labeled c1 through ck. Additionally, there are n students, labeled s1 to sn, attending these k courses. It's possible for a student to attend multiple on-site courses, and each course will have a variety of students enrolled. (20 points)
(b) Assuming a viable solution is found for part (a) where each student is enrolled in exactly m courses, there arises a need for a student representative for each course from among the enrolled students. However, any single student can represent at most r (where r is less than m) courses in which they are enrolled. Develop an algorithm to check whether it is possible to appoint such representatives, building on the solution from part (a) as a foundation. Prove your algorithm is correct by making an if-and-only-if claim.
Q6. Given the below graph solve the below questions using scaled version of Ford-Fulkerson. (15 points)
a) Give the Δ and path selected at each iteration.
b) Draw the final network graph and the residual graph c) Find the maxflow and mincut
Q7:The following graph G has labeled nodes and edges between them. Each edge is labeled with its capacity. (10 points)
(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?
(c) What is the min-cut?
Q8. You are provided with a flow network where each edge has a capacity of one. This network is represented by a directed graph G = (V, E), including a source node s and a target node t. Additionally, you are given a positive integer k. The objective is to remove k edges to achieve the greatest possible reduction in the maximum flow from s to t in G. Your task is to identify a subset of edges F within E, where the size of F equals k, and removing these edges from G results in a new graph G' = (V, E-F) where the maximum flow from s to t is minimized. Propose a polynomial-time strategy to address this issue.
Furthermore, consider if the capacities of the edges are greater than one, and discuss whether your strategy still ensures the lowest possible maximum flow. (20 points)
1 file (1.1MB)
