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: Q1E (page 106)

Perform a depth-first search on the following graph; whenever there’s a choice of vertices, pick the one that is alphabetically first. Classify each edge as a tree edge or back edge, and give the pre and post number of each vertex.

Short Answer

Expert verified

In the given problem, applieddepth-first search where the order of traverse isABCFEIDGH .

In order first we get the pre vertices of all and then get post vertex of the graph. Which are mentioned in the above diagram. A(1,16),B(2,11),C(3,10),F(4,9),E(5,6),I(7,8),D(13,18),G(14,17),H(15,16)

Step by step solution

01

Properties of DFS

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

Some properties ofdepth-first search are as follows:

  1. Using DFT we can verify that the graph is connected or not it means it detects the cycle present in the graph or not.
  2. We can find out the number of connected components by using depth-first search.
  3. Here we are using stack as a data structure.

The time complexity of list is O(V+E).

The time complexity of matrix isO(V2) .

It contains various edge they aretree edge, forward edge, back edge, or cross edge all the edges are explain below:

Tree edge: The graph obtained by traversing while using depth first search is called its tree edge.

Forward edge: the edge(u,v)where u is descendant and it is not part of depth first search is called forward edge.

Back edge: the edge (u,v)where u is ancestor and it is not part of depth first search is called forward edge.

02

Trace the graph

While traversing the graph by depth-first search firstly we get the vertices A, from A there are two options B and E and through A we must go to B.

From vertices B we have again two options they are C and E take C as our next vertices then F then by word depth first search going through node E, as there from F there are again two options they are E and I as mentioned in question traverse alphabetically so here after E, F comes that’s why go to F. and from F go to E and at last visit at I. also it contains a different graph that is contain nodes D,G,H. start from the source node D going in a alphabetic orderdepth first searchtraverse G and then H. here in the diagram the edge AB in black color is the main edge called tree edge.

The edge in blue color for example edge AF is called back edge, and the edge BE is called as forward edge.

Now, draw the graph traverse by depth-first search.


Hence, after applying depth-first search where the order of traverse is ABCFEIDGH.

03

Write the vertices

The tree edges are in the graph after traversing AB,BC,CF,EF,FI,DG,GH

And the back edges are as follows AE, BE and DH.

The pre and post-number of each vertex are given as,A(1,12) where

1 is pre vertex and 12 is post vertex.

In order first we get the pre vertices of all and then get post vertex of the graph. Which are mentioned in the above diagram.A(1,16),B(2,11),C(3,10),F(4,9),E(5,6),I(7,8),D(13,18),G(14,17),H(15,16)

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

Biconnected componentsLet G=(V,E) be an undirected graph. For any two edgese,e'∈E,, we’ll saye:e'if eithere=e'or there is a (simple) cycle containing both e and e'.

a. Show that : is an equivalence relation (recall Exercise 3.29) on the edges.

The equivalence classes into which this relation partitions the edges are called the biconnected components of G . A bridge is an edge which is in a biconnected component all by itself.

A separating vertexis a vertex whose removal disconnects the graph.

b. Partition the edges of the graph below into biconnected components, and identify the bridges and separating vertices.

Not only do biconnected components partition the edges of the graph, they almost partition the vertices in the following sense.

c. Associate with each biconnected component all the vertices that are endpoints of its edges. Show that the vertices corresponding to two different biconnected components are either disjoint or intersect in a single separating vertex.

d. Collapse each biconnected component into a single meta-node, and retain individual nodes for each separating vertex. (So there are edges between each component node and its separating vertices.) Show that the resulting graph is a tree.

DFS can be used to identify the biconnected components, bridges, and separating vertices of a graph in linear time.

e. Show that the root of the DFS tree is a separating vertex if and only if it has more than one child in the tree.

f. Show that a non-root vertex v of the DFS tree is a separating vertex if and only if it has a child v' none of whose descendants (including itself) has a back edge to a proper ancestor of v .

g. For each vertex u define:

Iowu=minpreuprew

Where (v,w) is a back edge for some descendant v of u.

(h) Show how to compute all separating vertices, bridges, and biconnected components of a graph in linear time.

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.

A bipartite graph is a graph G=(V,E)whose vertices can be partitioned into two sets (V=V1V2andV1V2=ϕ) such that there are no edges between vertices in the same set (for instance, if , then there is no edge between and ).

(a) Give a linear-time algorithm to determine whether an undirected graph is bipartite.

(b) There are many other ways to formulate this property. For instance, an undirected graph is bipartite if and only if it can be colored with just two colors. Prove the following formulation:

an undirected graph is bipartite if and only if it contains no cycles of odd length.

(c) At most how many colors are needed to color in an undirected graph with exactly one odd length?

The chapter suggests an alternative algorithm for linearization (topological sorting), which repeatedly removes source nodes from the graph (page 101). Show that this algorithm can be implemented in linear time.

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

Recommended explanations on Computer Science Textbooks

Databases

Read Explanation

Game Design in Computer Science

Read Explanation

Cloud Services

Read Explanation

Data Structures

Read Explanation

Big Data

Read Explanation

Fintech

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