Graph - DSA: Minimum Spanning Tree - Theory

Welcome to the foundational study of Minimum Spanning Trees (MST) in graph theory. This chapter introduces the core concepts of spanning trees, graph properties, tree definitions, edge weight minimization, and sets the stage for advanced algorithms like Prim's and Kruskal's.

1. Problem Statement: What is a Spanning Tree?

When working with graphs in computer science and network design, we often face scenarios where we need to connect all nodes together using a subset of edges without creating any cycles, while minimizing cost.

• Input Graph: An undirected, weighted graph containing $N$ nodes and $M$ edges.
  • Weights can be equal or different.
  • There is no strict fixed relationship between $N$ and $M$ in a general graph.
• Goal: Extract a sub-graph (a tree) that satisfies strict structural rules while including every single node from the original graph.

2. Formal Definition of a Spanning Tree

A Spanning Tree of a connected, undirected graph is a sub-graph that is a tree and connects all the vertices of the graph together.

Core Structural Rules:

1. Exact Vertex Count: It must contain all $N$ nodes of the original graph.
2. Exact Edge Count: It must contain exactly $N - 1$ edges.
3. Connectivity: All nodes must be reachable from one another (it forms a single connected component with zero cycles).

Spanning Tree Structural Properties:
  Nodes = N
  Edges = N - 1
  Cycles = 0 (Acyclic)
  Reachability = All nodes fully connected

3. Visualizing Spanning Trees from a Graph

Consider an undirected graph with 5 nodes and 6 edges. Because multiple paths exist between nodes, we can select different subsets of $N-1$ ($5-1 = 4$) edges that still keep all 5 nodes connected.

Example Spanning Tree 1:

• Nodes: $0, 1, 2, 3, 4$ (5 nodes)
• Edges Selected: 4 edges connecting the nodes into a single tree structure.
• Edge Weights Example: $6, 2, 5, 3$
• Total Weight Sum: $6 + 2 + 5 + 3 = 16$

Example Spanning Tree 2:

• Nodes: $0, 1, 2, 3, 4$ (5 nodes)
• Edges Selected: A different set of 4 edges.
• Edge Weights Example: $2, 8, 3, 7$
• Total Weight Sum: $2 + 8 + 3 + 7 = 20$

Note: A graph can have multiple valid spanning trees (sometimes one, sometimes many), depending entirely on the graph's topology and edge configurations.

4. Defining the Minimum Spanning Tree (MST)

While any tree satisfying the $N$ nodes and $N-1$ edges rule is a spanning tree, the Minimum Spanning Tree (MST) is a specific optimization of it.

• Definition: A Minimum Spanning Tree is a spanning tree in which the sum of all its edge weights is minimized.
• Key Distinctions:
  • Every MST is a Spanning Tree.
  • Not every Spanning Tree is a Minimum Spanning Tree.

5. Step-by-Step MST Verification Example

Imagine you are given a graph and you construct a candidate tree:

1. Connect node 1 to 4 (Weight: 1)
2. Connect node 1 to 2 (Weight: 2)
3. Connect node 2 to 3 (Weight: 3)
4. Connect node 3 to 5 (Weight: 4)
5. Connect node 5 to 6 (Weight: 7)

Sum Calculation:

If no other combination of $N-1$ edges yields a lower sum than $17$, this candidate tree qualifies as the Minimum Spanning Tree.

6. Roadmap to Solving MSTs: Upcoming Algorithms

To compute the Minimum Spanning Tree programmatically without manually inspecting every single possible tree combination, we use specialized graph algorithms:

• Prim's Algorithm: Grows the MST starting from an arbitrary node by greedily picking the minimum weight edge connected to the visited set.
• Kruskal's Algorithm: Sorts all graph edges in increasing order of weight and greedily adds edges while avoiding cycles using a Disjoint Set Data Structure.

7. Summary and Key Takeaways

• Graph Foundation: An undirected, weighted graph consists of $N$ nodes and $M$ edges.
• Spanning Tree Definition: A sub-tree containing all $N$ nodes and exactly $N - 1$ edges with complete inter-node reachability.
• Multiple Spanning Trees: A single graph can yield multiple valid spanning trees depending on edge selections.
• MST Optimization: The Minimum Spanning Tree (MST) is the unique or non-unique spanning tree that possesses the absolute minimum sum of edge weights.
• Non-Uniqueness: A graph can have more than one valid MST if multiple trees share the exact same minimum weight sum.
• Algorithmic Path Ahead: MST problems are efficiently solved in polynomial time using Prim's Algorithm or Kruskal's Algorithm.
• Disjoint Set Prerequisite: Understanding Kruskal's algorithm requires a robust grasp of the Disjoint Set Union (DSU) data structure.