Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 3: Q15E (page 108)

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

Expert verified

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

01

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.

02

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.

03

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

You are given a tree T=(V,E) (in adjacency list format), along with a designated root node r∈V. Recall that u is said to be an ancestor of v in the rooted tree if the path from r to v in T passes through u.

You wish to reprocess the tree so that queries of the form “is u an ancestor v?” can be answered in constant time. The pre-processing itself should take linear time. How can this be done?

In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction (OR) of two literals (a literal is a Boolean variable of or the negation of a Boolean variable). You are looking for a way to assign a valuetrueorfalseto each of the variables so that all clauses are satisfied- that is, there is at least one true literal in each clause. For example, here’s an instance of 2SAT:

x1∨x2¯∧x1¯∨x3¯∧x1∨x2∧x3¯∨x4∧x1¯∨x4

This instance has a satisfying assignment: set x1,x2,x3, and x4 totrue, false, false,andtrue,respectively.

  1. Are there other satisfying truth assignments of this 2SAT formula? If so, find them all.
  2. Give an instance of 2SAT with four variables, and with no satisfying assignment.

The purpose of this problem is to lead you to a way of solving 2SAT efficiently by reducing it to the problem of finding the strongly connected components of a directed graph. Given an instance l of 2SAT with n variables and m clauses, construct a directed graph GI=V,E as follows.

  • GIhas 2nnodes, one for each variable and its negation.
  • GIhas 2m edges: for each clause α∨βof l (where α,βare literals), G1has an edge from the negation of α to β, and one from the negation ofβ to α.

Note that the clause α∨βis equivalent to either of the implications α¯⇒β or β¯⇒α. In this sense, data-custom-editor="chemistry" GI records all implications in l .

(C). Carry out this construction for the instance of 2SAT given above, and for the instance you constructed in (b).

(d). Show that if GI has a strongly connected component containing both x and X¯ for some variable x , then l has no satisfying assignment.

(e). Now show the converse of (d): namely, that if none of GI’s strongly connected components contain both a literal and its negation, then the instance l must be satisfiable.(Hint: Assign values to the variables as follows: repeatedly pick a sink strongly connected component of GI. Assign valuetrueto all literals in the sink, assignfalseto their negations, and delete all of these. Show that this ends up discovering a satisfying assignment.)

(f). Conclude that there is a linear-time algorithm for solving 2SAT.

Run the strongly connected components algorithm on the following directed graphs G. When doing DFS on GR: whenever there is a choice of vertices to explore, always pick the one that is alphabetically first.

In each case answer the following questions.

(a) In what order are the strongly connected components (SCCs) found?

(b) Which are source SCCs and which are sink SCCs?

(c) Draw the “metagraph” (each meta-node is an SCC of G).

(d) What is the minimum number of edges you must add to this graph to make it strongly connected

The reverse of a directed graph G = (V,E) is another directed graphGR=(V,ER) on the same vertex set, but with all edges reversed that is,ER={(v,u):(u,v)∈E} . Give a linear-time algorithm for computing the reverse of a graph in adjacency list format.

You are given tree T=(V,E) along with a designated root node r∈V. The parent of any node V≠r, denoted p(V), is defined to be the node adjacent to v in the path from r to v . By convention, p(r)=r. For k>1, define pk(v)pk-1(pv)andp1(v)=p(v)(so pk(v)is the k th ancestor of v ). Each vertex v of the tree has an associated non-negative integer label l(v). Given a linear-time algorithm to update the labels of all the vertices T according to the following rule: lnew(v)=l(plvv).
See all solutions

Recommended explanations on Computer Science Textbooks

Cloud Services

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Systems

Read Explanation

Databases

Read Explanation

Big Data

Read Explanation

Problem Solving Techniques

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free