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-time 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. Assume that the Town Hall sits at 1 single intersection . The mayor's claim in (b) is the following: If you can get to another intersection, call it u, from the Town Hall intersection, then you can get back to the Town Hall intersection from u Note, linear time means O(n+m) where n IV and m E 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-time 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. Assume that the Town Hall sits at 1 single intersection . The mayor's claim in (b) is the following: If you can get to another intersection, call it u, from the Town Hall intersection, then you can get back to the Town Hall intersection from u Note, linear time means O(n+m) where n IV and m E
