What is a spanning tree of a graph?
a) A subgraph that includes all the vertices of the graph and is a tree
b) A subgraph that contains only leaf nodes
c) A graph where all edges have equal weights
d) A tree where every vertex has the same degree
Answer:
a) A subgraph that includes all the vertices of the graph and is a tree
Explanation:
A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree, meaning it is connected and has no cycles. A spanning tree has exactly n-1 edges, where n is the number of vertices in the graph.
Spanning trees are important in network design and optimization problems. In weighted graphs, the minimum spanning tree (MST) is the spanning tree with the smallest possible sum of edge weights.
Algorithms like Kruskal’s and Prim’s are used to find the minimum spanning tree in weighted graphs.
Reference:
DSA (Data Structures and Algorithms) MCQ Questions and Answers