Spanning Tree and Minimum Spanning Tree

A Spanning Tree of a connected graph is a subgraph that:

• Includes all the vertices of the graph.
• Is connected (there's a path between every pair of vertices).
• Contains no cycles (acyclic).
• Has exactly V − 1 edges, where V = number of vertices.

Think of it like a backbone network in a company: you need to connect all computers (vertices) using ethernet cables (edges), but you want to avoid creating loops (cycles) because loops cause broadcast storms and wasted cable. You use exactly enough cables to keep everyone connected, but no more.

Why Spanning Tree is Important?

A spanning tree ensures the minimum structure needed to connect all nodes. It's widely used in:

• Network Design: Connecting routers/switches efficiently.
• Broadcasting: Sending data to all nodes without duplication.
• Clustering: Grouping similar data points.
• Maze Generation: Creating perfect mazes with only one solution path.

Properties of Spanning Tree

Example: Spanning Tree

Consider the following connected graph:

    A
   / \
  B---C
   \ /
    D

Vertices: A, B, C, D

Edges: A-B, A-C, B-C, B-D, C-D

One possible spanning tree:

Edges: A-B, A-C, C-D

    A
   / \
  B   C
       \
        D

This uses 3 edges for 4 nodes, exactly V-1 = 4-1 = 3 edges.

Another possible spanning tree:

Edges: A-B, B-C, B-D

    A
   /
  B
 / \
C   D

Both are valid spanning trees. There are many possible spanning trees for the same graph.

How Many Spanning Trees Are Possible?

• For a complete graph (every vertex connected to every other vertex), the number of spanning trees is given by Cayley's formula:

  T(n) = n^(n-2)  for n vertices

• Examples:
  • 3 nodes → 3^(3-2) = 3 possible spanning trees.
  • 4 nodes → 4^(4-2) = 16 possible spanning trees.
  • 5 nodes → 5^3 = 125 possible spanning trees.
• For other graphs, you may use the Matrix-Tree Theorem (Laplacian Matrix) to count spanning trees.

Types of Spanning Trees

Applications of Spanning Trees

• Computer Networks: Efficient routing between switches/routers.
• Telecommunication: Laying cables with minimum length.
• Electrical Grid: Connecting substations with minimal wiring.
• Clustering: In AI and ML (hierarchical clustering).
• Maze Generation: Creating a perfect maze with only one solution.

Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a spanning tree of a connected, weighted graph that connects all vertices with the minimum possible total edge weight and no cycles.

Think of it like a cost optimization problem: you need to connect all cities (vertices) with roads (edges), but each road has a construction cost (weight). You want to build the cheapest possible network that still allows travel between every pair of cities.

Why MST is Useful?

MST is used when:

• You want to connect everything (like cities, computers, or networks).
• You want to spend as little as possible (minimize cost/length).
• You want to find a minimum-cost backbone network.

Properties of Minimum Spanning Tree (MST)

1. Connects All Vertices: An MST includes every vertex from the original graph. There are no isolated nodes, meaning you can reach any node from any other node.
2. Has Exactly V − 1 Edges: If the original graph has V vertices, the MST will always have V-1 edges. Adding any more edges would create a cycle, which is not allowed in a tree.
3. Contains No Cycles: As a type of tree, MST is acyclic. Any cycle would violate the "minimum" condition because removing one edge from the cycle can reduce the total weight.
4. Minimizes Total Edge Weight: Out of all possible spanning trees, the MST has the smallest possible total weight when you sum up the weights of its edges.
5. Subgraph of the Original Graph: The MST is formed by selecting some edges of the original graph (not adding new ones). It's a subset of the original graph's edges.
6. Uses Smallest Available Edges Carefully: The smallest edge that doesn't form a cycle is always a candidate for the MST. This idea is used in Kruskal's and Prim's algorithms.
7. Removing an Edge Disconnects the MST: Since the MST has the minimum number of edges needed to stay connected, removing any edge from it will disconnect the graph.
8. Does Not Necessarily Give the Shortest Path: While the MST connects all nodes with minimal cost, it doesn't ensure the shortest path between any two nodes. That's what Dijkstra's or Bellman-Ford algorithm is for.
9. Exists Only in Connected Graphs: If the graph is not connected (i.e., some nodes can't reach others), you cannot have a single MST. Instead, each connected component will have its own MST, forming a minimum spanning forest.

Example: Finding a Minimum Spanning Tree

Consider the following graph:

    A --(2)-- B
    |         |
   (3)       (4)
    |         |
    C --(1)-- D
    |         |
   (5)       (6)
    |         |
    E --(7)-- F

We want to find the Minimum Spanning Tree (MST) using Kruskal's Algorithm.

Step-by-Step Solution (Kruskal's Algorithm)

Step 1: Sort all edges by weight

Step 2: Initialize Union-Find

Each vertex is its own component: {A}, {B}, {C}, {D}, {E}, {F}

Step 3: Process edges in order

Final MST Edges: C-D (1), A-B (2), A-C (3), C-E (5), D-F (6)

Total Cost: 1 + 2 + 3 + 5 + 6 = 17

Visual Representation of MST

    A --(2)-- B
    |
   (3)
    |
    C --(1)-- D
    |         |
   (5)       (6)
    |         |
    E         F

This tree connects all 6 vertices with 5 edges, total weight 17.

Algorithms for Minimum Spanning Tree

Here's a list of algorithms used to find Minimum Spanning Tree (MST):

Complexity Comparison of MST Algorithms

Operations on Spanning Trees

• Find a spanning tree: Usually by DFS or BFS traversal.
• Create a spanning tree with weight logic: Leads to Minimum Spanning Tree.
• Optimize network paths: Using only V-1 connections (MST).
• Add/Remove edges: Maintain tree property (no cycles, connected).

Applications of Minimum Spanning Tree (MST)