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: Q30E (page 112)

On page 102, we defined the binary relation “connected” on the set of vertices of a directedgraph. Show that this is an equivalence relation(see Exercise 3.29), and conclude that it partitions the vertices into disjoint strongly connected components.

Short Answer

Expert verified

It can be shown that the binary relation “connected” on the set of vertices of a directed graph is an equivalence relation and yes, it partitions the vertices into disjoint strongly connected components.

Step by step solution

01

Explain the Equivalence relation

A relation is said to be in equivalence only if the relation satisfies reflexive, symmetry, and transitive properties.

02

Show that the given relation is the equivalence relation

Consider a set S that has the partitions of an undirected graph. Consider any two vertices x and y in the undirected graph.

From the solution of Exercise 3.29, the binary connected relation of the connected relationship satisfies reflexivity, symmetry, and transitivity. So, it is an equivalence relation.

The strongly connected component is the equivalence class corresponding to this relation.

Thus, it partitions the vertices into disjoint strongly connected components.

Therefore, It is shown that the binary relation “connected” on the set of vertices of a directed graph is an equivalence relation and yes, it partitions the vertices into disjoint strongly connected components.

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

Give an efficient algorithm which takes as input a directed graph G(V,E)and determines whether or not there is a vertexs∈V from which all other vertices are reachable.

Infinite paths.Let G=(V,E) be a directed graph with a designated “start vertex” s∈V,asetVG⊆V, a set of “good” vertices, and a set VB⊆V of “bad” vertices. An infinite trace of is an infinite sequence of vertices vi∈V such that (1)v0=s, and (2) for all i≥0, (vi,vi+1)∈E. That is, p is an infinite path in G starting at vertex s. Since the setV of vertices is finite, every infinite trace of Gmust visit some vertices infinitely often.

  1. If p is an infinite trace, let Inf(p)⊆V be the set of vertices that occur infinitely often in p. Show that Inf(p) is a subset of a strongly connected component of G.
  2. Describe an algorithm that determines if role="math" G has an infinite trace.
  3. Describe an algorithm that determines if G has an infinite trace that visits some good vertex in VG infinitely often.
  4. Describe an algorithm that determines if role="math" localid="1659627728759" G has an infinite trace that visits some good vertex in VG infinitely often, but visits no bad vertex in VB infinitely often.

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 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.

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?
See all solutions

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Read Explanation

Computer Systems

Read Explanation

Databases

Read Explanation

Computer Programming

Read Explanation

Computer Organisation and Architecture

Read Explanation

Big Data

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