Spanning Tree

[qingquan-li]

1. Spanning Tree

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree. Essentially, a spanning tree connects all the vertices together without any cycles and with the minimum possible number of edges. In a connected graph with V vertices, any spanning tree will have V-1 edges.

The primary purpose of a spanning tree is to ensure that all vertices are connected in a way that minimizes complexity (no cycles) and maximizes reachability (every vertex is included).

Key Characteristics of a Spanning Tree:

1. Contains All Vertices: A spanning tree must include every vertex of the original graph.

2. Minimum Number of Edges: It has exactly V-1 edges, where V is the number of vertices in the graph. This is the minimum number of edges required to connect all vertices without forming a cycle.

3. No Cycles: A spanning tree does not contain any cycles. It is a tree, which by definition is an acyclic connected graph.

4. Connected: The spanning tree is connected, meaning there's a path between every pair of vertices.

5. Not Necessarily Unique: A graph can have more than one spanning tree. The number of different spanning trees can vary greatly depending on the structure of the original graph.

Applications:

• Network Design: Spanning trees are vital in network design, such as designing a minimal cost network, Ethernet protocol, and more.
• Cluster Analysis: In data science, it can be used for cluster analysis in unsupervised machine learning.
• Minimum Spanning Tree (MST): Algorithms like Kruskal’s and Prim’s are used to find a spanning tree with the minimum sum of edge weights, which is useful in various optimization scenarios.

Types of Spanning Trees:

• Minimum Spanning Tree: A spanning tree with the minimum total edge weight. It's a common variant used in optimization problems.
• Maximum Spanning Tree: A spanning tree with the maximum possible total edge weight.

In summary, spanning trees are a fundamental concept in graph theory with practical applications in various fields, particularly in network design and optimization. They provide a way to maintain the connectivity of a graph while minimizing complexity and potential redundancy.

2. Minimum Spanning Tree (MST)

1. Definition of MST: A minimum spanning tree is a special kind of spanning tree where the sum of the weights of the edges in the tree is minimized. In other words, among all possible spanning trees, the one with the smallest total edge weight is chosen.

2. Properties of MST:

   • Includes all vertices of the original graph. (same as spanning tree)
   • Contains exactly (V - 1) edges. (same as spanning tree)
   • Is acyclic. (same as spanning tree)
   • The total weight of all the edges in the minimum spanning tree is as small as possible.
   • Often, but not necessarily, unique. There can be more than one minimum spanning tree in a graph with equal total weight.

3. Purpose of MST: The primary purpose of the minimum spanning tree is to minimize the cost of connecting all vertices. This is particularly useful in network design and optimization problems.

Key Differences between Spanning Tree and Minimum Spanning Tree

• Weight Consideration: The main difference between a general spanning tree and a minimum spanning tree is the consideration of edge weights. A minimum spanning tree specifically looks for a tree that minimizes the total weight, while a spanning tree is simply concerned with connecting all vertices in a tree structure without regard to edge weights.
• Applications: While both are used to connect all vertices, MSTs are particularly useful in scenarios where cost, length, or efficiency matters, like in designing efficient road networks, network communications, or electrical wiring.

3. Example: Original Graph -> Spanning Tree / Minimum Spanning Tree

Original Graph

Imagine a graph with 4 nodes (A, B, C, D) and weighted edges between them.

A --3-- B
| \     |
4  1    5
|    \  |
C --2-- D

Spanning Tree

A possible spanning tree for this graph might be:

A    B
| \  |
|  \ |
C    D

This spanning tree includes all vertices and is acyclic. It uses the edges AC, AD, and BD (or any other combination that maintains connectivity without cycles).

Minimum Spanning Tree

The minimum spanning tree, considering the weights, would be:

A --3-- B
  \    
    1   
      \
C --2-- D

This tree uses the edges AD, AB, and CD. The total weight is 1 (AD) + 2 (CD) + 3 (AB) = 6, which is the minimum possible weight to connect all the vertices.

4. Build a Minimum Spanning Tree Using Prim's Algorithm and Kruskal's Algorithm

4.1 Building MST using Prim's Algorithm

Prim's algorithm builds the MST by growing the spanning tree one vertex at a time, starting from any arbitrary vertex, and at each step, adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree.

Given a graph:

• The vertices are labeled A, B, C, D, and E.
• The edges have weights as indicated.

     2
A ------- B
| \     / |
|  \4  /1 |
|   \ /   |
6    C    3
|   / \   |
|  /5  \3 |
| /     \ |
D ------- E
     7

Steps of Prim's Algorithm (Starting from Vertex A):

1. Initialization: Start with vertex A.
2. Step 1: Add the edge with the lowest cost from A. The edge A-B (cost 2) is chosen.
3. Step 2: Now, consider all edges from A and B to other vertices. The edge B-C (cost 1) is the cheapest.
4. Step 3: Next, consider all edges from A, B, and C. The edge C-E (cost 3) is the cheapest.
5. Step 4: Finally, consider the remaining edges. The edge C-D (cost 5) is now the cheapest available edge.
6. All vertices are now included in the MST.

     2
A ------- B
        /
       /1 
      /
     C
    / \
   /5  \3
  /     \
 D        E

(Both Prim's and Kruskal's algorithms will yield the same MST)

4.2 Building MST using Kruskal's Algorithm

Kruskal's algorithm builds the MST by sorting all the edges of the graph by their weight and adding them one by one, skipping any edge that would create a cycle.

Given the same graph as Prim's Algorithm:

     2
A ------- B
| \     / |
|  \4  /1 |
|   \ /   |
6    C    3
|   / \   |
|  /5  \3 |
| /     \ |
D ------- E
     7

Steps of Kruskal's Algorithm:

1. Sort all edges: Sort edges by weight: (B-C, 1), (A-B, 2), (C-E, 3), (A-C, 4), (C-D, 5), (A-D, 6), (D-E, 7).
2. Step 1: Add the smallest edge B-C.
3. Step 2: Add the next smallest edge A-B.
4. Step 3: Add the next smallest edge C-E.
5. Step 4: Skip the next edge A-C (since it creates a cycle with A-B-C).
6. Step 5: Add the next edge C-D.
7. Step 6: Skip A-D and D-E (as they would create cycles).

Resulting the same Minimum Spanning Tree:

     2
A ------- B
        /
       /1 
      /
     C
    / \
   /5  \3
  /     \
 D        E