1 of 31

Trees in Graph Theory

Dr. Avipsita Chatterjee

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

1

1/31/2025

2 of 31

Introduction to Trees

​

  • Tree- a directed, acyclic structure of linked nodes.
      • Directed- one-way links between nodes (no cycles)
      • Acyclic- no path wraps back around to the same node twice (typically represents hierarchical data)

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

2

1/31/2025

3 of 31

Definition and Terminology

  • Definition: A tree is a connected, acyclic, undirected graph. Formally, a graph T = (V , E ) is a tree if:
      • T is connected (a path exists between any two vertices).
      • T contains no cycles.
  • Equivalent Definitions:
      • A graph T is a tree if and only if it has exactly n − 1 edges for n
      • vertices.
      • There exists a unique path between any two vertices in T . Removing any edge from T disconnects it.
      • Adding any edge to T creates exactly one cycle.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

3

1/31/2025

4 of 31

Definition and Terminology

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

4

1/31/2025

5 of 31

Definition and Terminology

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

5

1/31/2025

6 of 31

Definition and Terminology

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

6

1/31/2025

7 of 31

Properties of Trees

Theorem: A Tree with n vertices has n − 1 edges.

Proof (Induction):

  • Base Case: A single-vertex tree has 0 edges.
  • Inductive Hypothesis: Assume every tree with n vertices has n − 1 edges.
  • Inductive Step: Adding a new vertex and connecting it with an edge maintains a tree structure and increases the edge count by 1.
  • Example Illustration:

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

7

1/31/2025

8 of 31

Exercise:

  1. Prove that every tree has at least one leaf (a vertex with degree 1).
  2. Find all spanning trees of the complete graph K4.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

8

1/31/2025

9 of 31

Types of Trees

​

  • Rooted Tree
  • Binary Tree
  • Spanning Tree
  • Binary Search Tree
  • Balanced Tree
  • Binary Heap/Priority Queue
  • Red-Black Tree

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

9

1/31/2025

10 of 31

Rooted Trees - Definition and Properties

  • Definition: A rooted tree is a tree with a designated root vertex. Every other vertex has a unique parent except the root.
  • Properties:
        • The root is the unique vertex with no parent.
        • Every edge in a rooted tree is directed away from the root.
        • The depth of a node is the number of edges from the root to that node.
        • The height of a tree is the maximum depth of any node.
  • Example of a Rooted Tree:

​

​

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

10

1/31/2025

11 of 31

Rooted Trees - Definition and Properties

  • Theorem: The number of edges in a rooted tree with n nodes is always n − 1.
  • Exercise:
    • Find the depth and height of the given tree.
    • Prove that every rooted tree with at least two vertices has at least one leaf.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

11

1/31/2025

12 of 31

Binary Trees

Definition: A binary tree is a rooted tree where each node has at most two children.

Types of Binary Trees:

  • Full Binary Tree: Every node has either 0 or 2 children.
  • Complete Binary Tree: All levels are fully filled except possibly the last.
  • Perfect Binary Tree: A complete binary tree where all leaf nodes are at the same depth.

​

  • Theorem: The number of leaf nodes in a full binary tree with n internal nodes is n + 1.
  • Example: Full Binary Tree

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

12

1/31/2025

13 of 31

Binary Trees

​

Exercise:

  • Prove that the height of a perfect binary tree with n nodes is log2(n + 1) − 1.
  • Find the minimum and maximum height of a binary tree with 15 nodes.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

13

1/31/2025

14 of 31

Spanning Trees - Definition and Basic Properties

Definition: A spanning tree of a graph G = (V , E ) is a subgraph that:

  • Includes all vertices of G .
  • Is a tree (connected and acyclic).
  • Contains exactly |V|− 1 edges.

Basic Properties:

  • Every connected graph has at least one spanning tree.
  • A spanning tree is a minimal subgraph that preserves connectivity. Removing any edge from a spanning tree disconnects the graph. Adding any edge to a spanning tree creates a unique cycle.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

14

1/31/2025

15 of 31

Spanning Trees - Definition and Basic Properties

Example: A Graph and Its Spanning Tree

​

Original Graph A Spanning Tree

​

​

​

​

​

​

​

​

​

​

​

  • Exercise:
  • Verify that the spanning tree has exactly |V | − 1 edges.
  • Find all possible spanning trees of a cycle graph C4.

​

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

15

1/31/2025

16 of 31

Properties and Theorems on Spanning Trees

  • Fundamental Theorem of Spanning Trees:
  • A connected graph with n vertices has at least one spanning tree.
  • If a graph has a cycle, at least one edge can be removed while maintaining a spanning tree.
  • Property 1: Unique Path Property In any spanning tree T of a graph G , there exists a unique path between any two vertices.
  • Property 2: Minimal Connectivity If any edge is removed from a spanning tree, the graph becomes disconnected.
  • Property 3: Maximum Acyclicity: If any new edge is added to a spanning tree, exactly one cycle is formed.
  • Example: Unique Path Property

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

16

1/31/2025

17 of 31

Properties and Theorems on Spanning Trees

​

​

​

​

  • Exercise:
  • Prove that a graph with n vertices and n − 1 edges that is connected must be a tree.
  • Construct spanning trees for a complete graph K4.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

17

1/31/2025

18 of 31

Spanning Trees in Weighted Graphs

Definition: A Minimum Spanning Tree (MST) of a weighted graph is a spanning tree that has the minimum possible total edge weight.

Applications:

    • Network Design (telecommunications, electrical networks)
    • Cluster Analysis (data science, machine learning)
    • Approximation Algorithms (for NP-hard problems like TSP)

Algorithms for Finding MST:

  • Kruskal’s Algorithm - Greedy algorithm that sorts edges by weight and adds edges while avoiding cycles.
  • Prim’s Algorithm - Starts from an arbitrary node and grows the tree

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

18

1/31/2025

19 of 31

Spanning Trees in Weighted Graphs

​

​

  • Example: Weighted Graph and Its MST

​

  • Weighted Graph: Minimum Spanning Tree:

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Exercise:

  • Prove that Kruskal’s algorithm produces an MST.
  • Find an MST for a complete graph with random weights.

​

​

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

19

1/31/2025

20 of 31

Proof of Kruskal’s Algorithm

  • Claim: Kruskal’s algorithm always produces an MST.
  • Proof (Greedy Choice and Safe Edge Property):
  • Step 1: Greedy Choice Property
  • ▶ Consider an MST T ∗ and the edge e added by Kruskal’s algorithm.
  • ▶ If e ∈ T ∗, we are done.
  • ▶ Otherwise, adding e forms a cycle. Removing the heaviest edge in the cycle still results in an MST.

​

  • Step 2: Safe Edge Property
  • ▶ Kruskal’s algorithm selects the minimum-weight edge that connects two disjoint components.
  • ▶ This ensures that each added edge is safe and maintains the MST structure.

​

  • Conclusion: By inductive argument, the algorithm constructs an MST by always selecting a safe edge.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

20

1/31/2025

21 of 31

Proof of Kruskal’s Algorithm

​

​

Exercise:

​

  • Prove that Kruskal’s algorithm maintains acyclic behavior at every step.
  • Demonstrate Kruskal’s execution on a 5-vertex graph.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

21

1/31/2025

22 of 31

Complexity Analysis of Kruskal’s Algorithm

Time Complexity Breakdown:

  • Step 1: Sorting the edges - Sorting E edges takes O(E log E ).
  • Step 2: Union-Find Operations - Each union or find operation takes O(α(V )) time using the Union-Find with path compression. - There are at most V − 1 union operations. - Total time: O(Eα(V )).

Overall Time Complexity:

  • O(E log E ) + O(Eα(V )) = O(E log E )

since α(V ) (inverse Ackermann function) grows very slowly. Comparison with Prim’s Algorithm:

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

22

1/31/2025

23 of 31

Complexity Analysis of Kruskal’s Algorithm

Exercise:

  • Compare Kruskal’s and Prim’s algorithms on a graph with 1000 vertices and 2000 edges.
  • Explain why Kruskal’s algorithm is preferred in disconnected graphs.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

23

1/31/2025

24 of 31

Prim’s Algorithm - Definition and Steps

Definition: Prim’s algorithm is a greedy algorithm that grows the Minimum Spanning Tree (MST) from a single starting vertex, adding the smallest edge that expands the tree.

​

Algorithm Steps:

  • Select an arbitrary starting vertex.
  • Maintain a priority queue of edges connecting the MST to the rest of the graph.
  • Repeatedly:
    • Pick the smallest weight edge that connects an MST vertex to a non-MST vertex.
    • Add this edge and the new vertex to the MST.
    • Update the priority queue with edges from the newly added vertex.
    • Stop when all vertices are included in the MST.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

24

1/31/2025

25 of 31

Prim’s Algorithm - Definition and Steps

​

  • Example:

​

Graph with Weights MST Using Prim’s Algorithm

​

​

​

​

​

​

​

​

​

Exercise:

  • Implement Prim’s algorithm using a priority queue.
  • Compare the performance of Prim’s algorithm with Kruskal’s on dense graphs.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

25

1/31/2025

26 of 31

Proof of Prim’s Algorithm

  • Claim: Prim’s algorithm always produces an MST.
  • Proof (Greedy Choice and Cut Property):
  • Step 1: Greedy Choice Property
  • Assume Prim’s algorithm has already built a partial MST T .
  • It picks the smallest edge crossing the cut (T, V − T ).
  • Let e = (u, v ) be this edge, and assume T ∗ is the optimal MST.
  • Step 2: Cut Property
  • If e ∈ T ∗, we are done.
  • If e ∈/ T ∗, adding e to T ∗ creates a unique cycle.
  • The heaviest edge in this cycle can be removed while keeping the tree connected.
  • This transformation does not increase total weight, proving correctness.
  • Conclusion: By mathematical induction, Prim’s algorithm constructs an MST by always picking a safe edge.

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

26

1/31/2025

27 of 31

Prim’s Algorithm

​

Exercise:

​

  • Prove that Prim’s algorithm works correctly for disconnected graphs.
  • Find an example where Prim’s and Kruskal’s algorithms produce different MSTs.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

27

1/31/2025

28 of 31

Complexity Analysis of Prim’s Algorithm

Time Complexity Breakdown:

  • Using a Priority Queue (Binary Heap):
  • Extracting the minimum edge: O(log V ) per vertex.
  • Updating the priority queue: O(log V ) per edge.
  • Total complexity: O(E log V ).
  • Using an Adjacency Matrix:
  • Finding the minimum edge takes O(V ).
  • Total complexity: O(V 2).
  • Comparison with Kruskal’s Algorithm:

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

28

1/31/2025

29 of 31

Complexity Analysis of Prim’s Algorithm

  • Kruskal’s is preferred for sparse graphs since it sorts edges first.
  • Prim’s (Binary Heap) is better for dense graphs since it operates directly on vertices.
  • Prim’s (Adjacency Matrix) is ideal for graphs where E ≈ V 2.

​

​

Exercise:

  • Compare Prim’s and Kruskal’s algorithms on a graph with 500 vertices and 1000 edges.
  • Explain why Prim’s algorithm is more efficient for connected graphs.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

29

1/31/2025

30 of 31

Comparison of MST Algorithms in Literature

  • Different MST Algorithms and Their Applications:

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

30

1/31/2025

31 of 31

Comparison of MST Algorithms in Literature

Key Observations:

    • Kruskal’s is best for edge-based processing, while Prim’s is best for vertex-based processing.
    • Bor˚uvka’s algorithm is useful for distributed computing frameworks. Reverse-Delete is the opposite of Kruskal’s but useful in certain edge-removal optimization cases.
    • Fibonacci Heap improves Prim’s performance, making it optimal for large graphs.
    • Chazelle’s algorithm is mostly of theoretical interest due to its complexity benefits.
    • Approximate MST algorithms trade accuracy for speed, useful in AI and networking.

Exercise:

    • Compare the performance of Kruskal’s and Prim’s algorithms on a 10,000-node graph.
    • Research how Bor˚uvka’s Algorithm is used in parallel computing.

​

Dr. Avipsita Chatterjee, I.E.M., Salt Lake

31

1/31/2025