Minimum Spanning trees

Prim’s algorithm
Lecture
 Spanning Trees
A connected sub graph H of given Graph G is said to be spanning tree iff
1. H contains all vertices of G.
2. H should contain (n-1) edges if G contains n vertices.

Question 1 Find number of spanning trees for the following graph:

 Spanning Trees
Question 2 Find number of spanning trees for the following graph:
 Spanning Trees
Question 3 Find number of spanning trees for the following graph:
 Spanning Trees
The number of spanning trees in a complete graph:
𝐒𝐓 𝑲𝒏 = 𝒏𝒏−𝟐

𝐒𝐓 𝑲𝟐 =
𝐒𝐓 𝑲𝟑 =
𝐒𝐓 𝑲𝟒 =
𝐒𝐓 𝑲𝟓 =
 Spanning Trees: Kirchoff’s Theorem
1 2 Find number of spanning trees for the following graph:

Step 1: Find adjacency matrix for the given graph.

3 4 0 1 1 1
𝑀= 1 0 0 1
1 0 0 1
1 1 1 0
Step 2: Replace all diagonal 0’s by its’ degree and non-diagonal 1’s by -1.
3 −1 −1 −1
𝑀 = −1 2 0 −1
−1 0 2 −1
−1 −1 −1 3
Step 3: Number of spanning tree = co-factor of any element.
2 0 −1
Co-factor (M11) = 0 2 −1
−1 −1 3

= 2(6-1)-1 (2) =8
 Spanning Trees: Kirchoff’s Theorem
1 2 Find number of spanning trees for the following graph:

Step 1: Find adjacency matrix for the given graph.

3 4 0 1 1 1
𝑀= 1 0 1 1
1 1 0 1
1 1 1 0
Step 2: Replace all diagonal 0’s by its’ degree and non-diagonal 1’s by -1.
3 −1 −1 −1
𝑀 = −1 3 −1 −1
−1 −1 3 −1
−1 −1 −1 3
Step 3: Number of spanning tree = co-factor of any element.
3 −1 −1
Co-factor (M11) = −1 3 −1
−1 −1 3

= 3(9-1) + 1 (-3-1) -1(1+3) = 16

 Minimum Cost Spanning Tree
20
1 2
60
30 40
50
3 10 4

Using Prim’s and Kruskal’s algorithm we can find out the minimum cost spanning tree
 Minimum Cost Spanning Tree: Prim’s Algorithm
1
70 Step 1: Choose any vertex and find adjacent of that vertex and take minimum of them
10
2 3
60
30 50
40
Step 2: Find adjacency vertices of new vertex and take minimum of these adjacent and
4 20 5 previous.

Step 3: Repeat step 2 until all the vertices are not covered.
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70
10 The edges in set A always form a single tree
b c
60 Starts from an arbitrary “root”: VA = {a}
30 50
40 At each step:
d 20 e Find a light edge crossing (VA, V - VA)
Add this edge to A
Repeat until the tree spans all vertices
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70
10 The edges in set A always form a single tree
b c
60 Starts from an arbitrary “root”: VA = {a}
30 50
40 At each step:
d 20 e Find a light edge crossing (VA, V - VA)
Add this edge to A
Repeat until the tree spans all vertices
 Minimum Cost Spanning Tree: Prim’s Algorithm
70
a Nodes distances in priority Queue : 0    
10 Q = {a, b, c, d, e}
b c
60 VA = 
30
40
50 Extract-MIN(Q)  a
d 20 e

VA = {a}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70

b
10
c
key [b] = 70  [b] = a
60
30 50
40
d 20 e 70    
Q = {b, c, d, e} VA = {a}
Extract-MIN(Q)  b
VA = {a, b}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70

b
10
c
key [b] = 70  [b] = a
60
30 50
40
d 20 e 70    
Q = {b, c, d, e} VA = {a}
Extract-MIN(Q)  b
VA = {a, b}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70

b
10
c
key [c] = 10  [c] = b
60 key [d] = 30  [d] = b
30 50
40 key [e] = 60  [e] = b
d 20 e

10, 30, 60
Q = {c, d, e} VA = {a, b}
Extract-MIN(Q)  c
VA = {a, b, c}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70

b
10
c
key [c] = 10  [c] = b
60 key [d] = 30  [d] = b
30 50
40 key [e] = 60  [e] = b
d 20 e

10, 30, 60
Q = {c, d, e} VA = {a, b}
Extract-MIN(Q)  c
VA = {a, b, c}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70
10
b c
60 key [d] = 30  [d] = b
30 50
40 key [e] = 50  [e] = c
d 20 e

30, 50
Q = { d, e} VA = {a, b, c}
Extract-MIN(Q)  d
VA = {a, b, c, d}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70
10
b c
60 key [d] = 30  [d] = b
30 50
40 key [e] = 50  [e] = c
d 20 e

30, 50
Q = { d, e} VA = {a, b, c}
Extract-MIN(Q)  d
VA = {a, b, c, d}
 Minimum Cost Spanning Tree: Prim’s Algorithm
a
70
10
b c
60
30 50
40 key [e] = 20  [e] = d
d 20 e

20
Q = { e} VA = {a, b, c, d}
Extract-MIN(Q)  e
VA = {a, b, c, d, e}
Q=
 Minimum Cost Spanning Tree: Prim’s Algorithm
1
7 6
2 3
2 6
6 6
4 5 3
7
4 8 5
Minimum Cost Spanning Tree: Prim’s Algorithm

Time Complexity:
Using Binary Min Heap: 𝑂[ 𝑉 + 𝐸 𝑙𝑜𝑔𝑉]
Using Fibonacci Min Heap: 𝑂[𝐸 + 𝑉𝑙𝑜𝑔𝑉]
Using Binomial Min Heap: 𝑂[ 𝑉 + 𝐸 ]
Minimum Cost Spanning Tree: Prim’s Algorithm
Thank You