Description
1.) (20 points each) Let G be an undirected graph, and let s and t be distinct vertices of G. Each edge in G is assigned one of two colors, white or gold. (Hint: For this question, you may modify the graph and make a new graph as long as the solution is still for the original graph).
(a.) Design an algorithm that determines if there is a path from s to t with edges of only one color (that is, a path containing either white edges only or gold edges only).
(b.) Design an algorithm that determines if there is a path from s to t such that all white edges appear before all gold edges in the path.
2.) (20 points each) The police department in the city of Computopia has made all streets one-way. The mayor contends that there is still a way to drive legally from any intersection in the city to any other intersection, but the opposition is not convinced. A computer program is needed to determine whether the mayor is right. However, the city elections are coming up soon, and there is just enough time to run a linear algorithm.
(a.) Formulate this problem graph-theoretically, and explain why it can indeed be solved in linear time.
(b.) Suppose it now turns out that the mayor’s original claim is false. She next claims something weaker: if you start driving from town hall, navigating one-way streets, then no matter where you reach, there is always a way to drive legally back to the town hall. Formulate this weaker property as a graph-theoretic problem, and carefully show how it too can be checked in linear time.
Solution:
3.) (20 points) There is a network of roads G = (V, E) connecting a set of cities V . Each road in E has an associated positive length ℓe. There is a proposal to add one new road to this network, and there is a list E′ of pairs of cities between which the new road can be built. Each such potential road e′ ∈ E′ has an associated length. As a designer for the public works department you are asked to determine the road e′ ∈ E′ whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.
