wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

We define D-Tree(G) as the tree obtained by applying the DFS algorithm on a graph G.
Consider the following statements regarding the same.

S1 : If G is an undirected graph, then every edge in D-Tree (G) is either a tree edge or a back edge.

S2 : If G is a undirected graph, then every edge in D-Tree(G) is either a tree edge, or a cross edge.

Which of the above statements are true ?

A
Both S1 and S2
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
Only S2
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
Only S1
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
D
None of these
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

The correct option is C Only S1
DFS of an undirected graph contains tree edges and back edges, but can never contain forward edges and cross edges.
Hence S1 is the only true statement.

flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Double Bar Graphs
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon