Past exam question: 2065 Shrawan (Regular / Back), Q9
Open in the Padhaiko appQuestion
Define directed undirected graph, spanning forest, minimum spanning trees.
Solution
1. Directed and Undirected Graphs:
- Directed Graph (Digraph): A graph in which every edge is an ordered pair with a one-way direction from tail to head ().
- Undirected Graph: A graph in which edges are unordered pairs , representing symmetric bidirectional connections.
2. Spanning Forest and Minimum Spanning Tree (MST):
- Spanning Forest: Given an undirected graph with connected components, a spanning forest is an acyclic subgraph spanning all vertices of that consists of one spanning tree for each connected component ( edges total).
- Minimum Spanning Tree (MST): For a connected, undirected, weighted graph, an MST is a spanning tree ( edges) whose sum of edge weights is minimum among all spanning trees (found by Kruskal's or Prim's algorithm).
Answer:
A directed graph has ordered one-way edges; an undirected graph has symmetric edges; a spanning forest comprises one spanning tree per connected component; and an MST is a minimum-total-weight spanning tree of a connected weighted graph.