Starting from:
$24.99
CSCI570 Homework9 Solution
1) There is a precious diamond that is on display in a museum at m disjoint time intervals. There are n security guards who can be deployed to protect the precious diamond. Each guard has a list of intervals for which he or she is available to be deployed. Each guard can be deployed to at most M time slots and has to be deployed to at least L time slots.Design an algorithm that decides if there is a deployment of guards to intervals such that each interval has either one or two guards deployed. (10 pts)
Note: We are only looking for the largest number of SPYs not the actual location of the words. No proof is necessary.
UNGRADED
4) In the network below, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if a feasible circulation exists or not. If it does, show the feasible circulation. If it doesnot, show the cut in the network that is the bottleneck. Show all your steps.
5) The following graph G is an instance of a circulation problem with demands. The edge weights represent capacities and the node weights (in parantheses) represent demands. A negative demand implies source.
(i) Transform this graph into an instance of max-flow problem.
(ii) Now, assume that each edge of G has a constraint of lower bound of 1 unit,
i.e., one unit must flow along all edges. Find the new instance of max-flow problem that includes the lower bound constraint.
6) Determine if it is possible for flow to circulate within the given network depicted as graph G. The demand values, indicated on vertices, represent either supply (if positive) or demand (if negative). Each edge also has specified lower bounds on flow and capacity. Demonstrate all necessary steps to ascertain if a feasible circulation exists within this graph. (20 pts)
(a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds.
(b) Reduce the Feasible Circulation problem obtained in part (a) to a Max Flow problem in a Flow Network.
(c) Solve the resulting Max Flow problem and explain whether there is a Feasible Circulation in the original G.
7) USC Admissions Center needs your help in planning paths for Campus tours given to prospective students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. On a busy day, let k be the number of campus tours that have to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let the tour have k starting locations A = {a1, a2, ..., ak} ⊆ V . From the starting locations, the groups are taken by a guide on a path through G to some ending location in B = {b1, b2, ..., bk} ⊆ V . Your goal is to find a path for each group i from the starting location, ai, to any ending location bj such that no two paths share any edges, and no two groups end in the same location bj .
(a) Design an algorithm to find k paths ai → bj that start and end at different vertices, such that they do not share any edges.
(b) Modify your algorithm to find k paths ai → bj that start and end in different locations, such that they do not share any edges or vertices.
Note: We are only looking for the largest number of SPYs not the actual location of the words. No proof is necessary.
UNGRADED
4) In the network below, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if a feasible circulation exists or not. If it does, show the feasible circulation. If it doesnot, show the cut in the network that is the bottleneck. Show all your steps.
5) The following graph G is an instance of a circulation problem with demands. The edge weights represent capacities and the node weights (in parantheses) represent demands. A negative demand implies source.
(i) Transform this graph into an instance of max-flow problem.
(ii) Now, assume that each edge of G has a constraint of lower bound of 1 unit,
i.e., one unit must flow along all edges. Find the new instance of max-flow problem that includes the lower bound constraint.
6) Determine if it is possible for flow to circulate within the given network depicted as graph G. The demand values, indicated on vertices, represent either supply (if positive) or demand (if negative). Each edge also has specified lower bounds on flow and capacity. Demonstrate all necessary steps to ascertain if a feasible circulation exists within this graph. (20 pts)
(a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds.
(b) Reduce the Feasible Circulation problem obtained in part (a) to a Max Flow problem in a Flow Network.
(c) Solve the resulting Max Flow problem and explain whether there is a Feasible Circulation in the original G.
7) USC Admissions Center needs your help in planning paths for Campus tours given to prospective students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. On a busy day, let k be the number of campus tours that have to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let the tour have k starting locations A = {a1, a2, ..., ak} ⊆ V . From the starting locations, the groups are taken by a guide on a path through G to some ending location in B = {b1, b2, ..., bk} ⊆ V . Your goal is to find a path for each group i from the starting location, ai, to any ending location bj such that no two paths share any edges, and no two groups end in the same location bj .
(a) Design an algorithm to find k paths ai → bj that start and end at different vertices, such that they do not share any edges.
(b) Modify your algorithm to find k paths ai → bj that start and end in different locations, such that they do not share any edges or vertices.
1 file (2.0MB)
