(20 pts.) One-way Streets. The police department in the city of Comtopia has made all streets...

Transcribed Image Text:

(20 pts.) One-way Streets. The police department in the city of Comtopia 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 (in terms of the number of roads and intersections). (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 in a graph-theoretic setting, and carefully show how it too can be checked in linear time. (20 pts.) One-way Streets. The police department in the city of Comtopia 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 (in terms of the number of roads and intersections). (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 in a graph-theoretic setting, and carefully show how it too can be checked in linear time.

Answer rating: 100% (QA)

a Formulating the problem graphtheoretically The problem can be represented as a directed graph wher... View the full answer