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

Given a graph G, F is a spanning tree of G, if
(i) F is subgraph of G containing all the nodes of G
(ii) F is an ordered forest containing tree T1,T2,...... Tn.
(iii) Ti contain all the nodes that are reachable in G from the root Ti and are not contained in Ti for some j<i of these.

A
(i) and (ii)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
(ii) and (iii)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
(i) and (iii)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
(i), (ii) and (iii)
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution

The correct option is D (i), (ii) and (iii)

A graph G, F is a spanning tree of G, if
(i) F is subgraph of G containing all the nodes of G.
(ii) F is an ordered forest containing tree T1,T2,...... Tn.

(iii) Ti contain all the nodes that are reachable in G from the root Ti and are not contained in Ti for some j<i of these.

All the options are true.

Spanning tree:-

A spanning tree is a subset of graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

A subgraph S of a graph G is a graph whose set of vertices and set of edges are all subsets of G. A spanning subgraph is a subgraph that contains all the vertices of the original graph.



flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Graphical Representation of a Linear Equation in Two Variables
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon