Discrete Mathematics Spanning Trees - Discrete Mathematics

What is a spanning tree in Discrete Mathematics?

The tree which includes all the vertices of the connected undirected graph G very minimally is known as a spanning tree. A single graph can have many spanning trees.

Example

Graph in Span

Spanning Tree

What is Minimum Spanning Tree?

When the assigned weight is less than or equal to the weight of all possible spanning tree of weighted, connected and undirected graph G, such a spanning tree is called as Minimum Spanning Tree (MST). The weight of the spanning tree is calculated by the total of all the weights that are assigned to each edge of the spanning tree.

Example

Minimum Spanning Tree

What is Kruskal's Algorithm?

An algorithm that is used for finding the minimum spanning tree of a connected weighted graph is known as Kruskal’s algorithm. A tree among the graph is identified which includes every vertex and where the total weight of all the edges in the tree is less than or equal to the spanning tree.

Algorithm

Step 1 – All the edges of the given graph G(V,E) are arranged in the non-decreasing order in accordance with the weight of the edge.

Step 2 – The smallest weighted edge from the graph is chosen and is checked if it forms a spanning tree earlier.

Step 3 – This edge is included to the spanning tree if there is no cycle, or else it is discarded.

Step 4 − Repeat Step 2 and Step 3 until (V−1) number of edges are left in the spanning tree.

Problem

For instance, identify the minimum spanning tree from the following graph G by using the Kruskal’s algorithm.

Kruskal Problem

Solution

The following table is constructed from the above graph:

Edge No.
Vertex Pair
Edge Weight
E1
(a, b)
20
E2
(a, c)
9
E3
(a, d)
13
E4
(b, c)
1
E5
(b, e)
4
E6
(b, f)
5
E7
(c, d)
2
E8
(d, e)
3
E9
(d, f)
14

In accordance with the weight of the Edge, the table is rearranged in ascending order.

Edge No.
Vertex Pair
Edge Weight
E4
(b, c)
1
E7
(c, d)
2
E8
(d, e)
3
E5
(b, e)
4
E6
(b, f)
5
E2
(a, c)
9
E3
(a, d)
13
E9
(d, f)
14
E1
(a, b)
20

Kruskal Adding Vertex edge

Kruskal Adding Vertex Edge

Kruskal Adding Vertex Edge

As all the edges are covered in the last figure, the algorithm is stopped and this is considered as the minimal spanning tree and the total weight of the spanning tree is (1+2+3+5+9)=20.

What is Prim's Algorithm?

The minimum spanning tree for a connected weighted graph by Prim’s algorithm, developed by the mathematicians Vojtech Jarnik and Robert C. Prim. In the Graph, the tree that includes every vertex and total weight of all the edges in the tree is less than or equal to every possible spanning tree. Prim’s algorithm works faster on dense graphs.

Algorithm

  • Randomly selected from the graph, the minimal spanning tree with single vertex is initialized.
  • Until all the vertices are included in the tree, step 3 and step 4 are repeated.
  • The edge that is not yet in the tree, but connects the edge with the tree is selected, such that the weight of the edge is minimal and even after including the edge, it does not form a cycle.
  • The selected edge and the vertex it connects are added to the tree.
  • Select an edge that connects the tree with a vertex not yet in the tree, so that the weight of the edge is minimal and inclusion of the edge does not form a cycle.

Problem

For instance, consider the following graph G and identify the minimum spanning tree using Prim’s algorithm

Prim

Solution

It is started with vertex ‘a’.

Prim Vertex a added

Prim vertex c b added

Prim vertex d e added

Prim vertex f added

The above graph is the minimum spanning tree and the total weight is (1+2+3+5+9)=20

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics