Question

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.

Short answer

a). This problem is solved in linear time is proved.

b). If mayor’s original claim is false. She next claims something weaker: if starts driving from town hall, navigating one-way streets, then no matter where to reach, there is always a way to drive legally back to the town hall, it can be checked in linear time is shown below.

Step-by-step solution

Linear time algorithm.

This problem is solved by taking the help of the algorithm of depth first search in a strongly connected component.Depth first search traversal takes linear time and the reversal of graph is also takes the linear timer for traversal.

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in downward direction one by one.

Strongly connected components in a directed graph shows that the where every vertex is reachable from every other vertex. The graph is strongly connected is only when the graph is directed graph.

Applying depth first search (linear time algorithm)

a).

This problem is proved by a directed graph where is the vertices of the graph and is the edges and each intersection is a vertex and there is an edge between intersections of if there is a road that goes directly from .Then there is a way to drive legally from any intersection to any other intersection is true if and only if, there is path from each vertex of graph to every other vertex. This is true if, and only if, the graph is Strongly connected, so this can be solved in linear time with DFS by determining if the graph is a single strongly connected component.

The mayor says 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

It can be proved by the concept of strongly connected graph whereStrongly connected components in a directed graph shows that the where every vertex is reachable from every other vertex. The graph is strongly connected is only when the graph is directed graph.

Depth First Search (DFS) is a application of graph traversal.

It always traverses downwards and uses the stack as a data structure, through this it traverses all vertices in downward direction one by one.

It follows the strongly connected components algorithm by using depth first search in it. Since depth first search is takes linear time and this is also follow the same.

The algorithm for this statement is given below,

1. In the starting all the vertices are unvisited.

2. Run depth first search from the source vertex. after completion of depth first search if there are unvisited vertex then claim it is a lie.

Otherwise it will get any other vertex from source vertex.

3. Make a reversal path, change the direction of all the edges.

4. Set all vertices as unvisited again.

5. Now again run depth first search from the starting vertex.

After completing the DFS traversal if there is any unvisited vertex then claim it is lie.Which shows that it will get from any vertex to any other vertex.

This algorithm will take linear time because the depth first search traversal and reversing of edges takes linear time.

Navigation from source to end vertex by considering it townhall.

b).

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.

Here, by using the same graph as in the first part and label the town hall , of the source vertex. This is true if, and only if, there is no path from to the vertex v , such that there is no path from v to s .

Then there must be no path from to a vertex outside of the connected component v of s. To determine if the graph has this property it must be label each vertex with the number of its connected component and then after that apply a depth first search from s vertex.

If s reaches to a vertex which is in a different connected component then the new claim is false.It follows the strongly connected components algorithm by using depth first search in it. Sohere 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. hence this is proved that it can also be checked in linear time.