Algorithms Test 5

Result

Algorithms Test 5

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
1 / -0

Which of the following statements are TRUE?
I. In a depth-ﬁrst search of an undirected graph G, every edge of G is either a tree edge or a back edge.
II. Forward and cross edges never occur in a depth-ﬁrst search of an undirected graph.
III. A directed graph is acyclic if and only if a depth-ﬁrst search yields no back edges.

A
I

B
I and II

C
II and III

D
All of the above

Solution

I. Depth search explores edge (u,v), it is in the direction from u to v, then v is undiscovered until that time, for otherwise the search would have explored this edge already in the direction from v to u. Thus, (u,v) becomes a tree edge. If the search explores (u,v) ﬁrst in the direction from v to u, then (u,v) is a back edge.
II. An undirected graph may entail some ambiguity in classification of edges, since (u,v) and (v,u) are really the same edge. Hence, forward and cross edges never occur in a depth-ﬁrst search of an undirected graph.
III. Suppose that a depth-ﬁrst search produces a back edge (u,v) Then vertex v is an ancestor of vertex u in the depth-ﬁrst forest. Thus, G contains a path from v to u, and the back edge (u,v) completes a cycle.
Question 2
1 / -0

Consider a graph G(V, E) where V is the vertices and E is the edge which is marked as tree edges in the depth-first traversal of a graph G. If V is 10 and E is 6 then the number of connected components in G is _____.

A
4-4

B
44-41

C
47-46

D
49-42

Solution

Data:
Vertices = V = 10
Edges = E = 6
Formula:
number of components = V - E
Calculation:
number of components = 10 - 6 = 4
Explanation:
If the Graph is connected, in DFS traversal some spanning Tree of Graph is visited.
So, number of edges is n-1 and the no of components = n - (n-1) = 1
If the Graph is not connected, DFS traversal is done on disconnected graphs.
For every disconnected component with say x vertices, we will get x-1 Tree edge.
When we sum up all vertices, we will get a total no of vertices. When we sum up all edges in spanning tree of each component,
Total number of vertices - Total number of the connected component
There Total connected component = V - E = 10 - 6 = 4