@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

MODULE-5
TREES

DISCRETE MATHEMATICS & GRAPH

THEORY

11-04-2023 Discrete Mathematics & Grapg Theory 1

TREES AND THEIR BASIC PROPERTIES

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

❑ A graph is a tree, if it is connected and has no cycle.
❑ Tree must be simple graph as loops and parallel edges form cycles.
❑ A vertex of degree 1 is called a terminal vertex or a leaf, the other vertices are called internal nodes.
❑ A tree is denoted by T .

Not a tree as it
contain cycle
Not connected so not tree,
but each component is a
tree and collectively called
(a)
forest.
(b)
11-04-2023 Discrete Mathematics & Grapg Theory 2
Theorems

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

1. In a tree, there is one and only one path between every pair of vertices

2. If in a graph G there is one and only one path between every pair of vertices then G is a tree

3. A tree with n vertices has n-1 edges

4. Any connected graph with n vertices and n-1 edges is a tree

Note: A disconnected graph with n vertices and n-1 edges need not be a tree

Minimally connected graphs

A graph is minimally connected if the removal of any one edge from it disconnects the graph.

Note:
(a) The complete graph Kn is not a tree when n > 2.

(b) The complete graph Kr,s is not a tree when r ≥ 2.

11-04-2023 Discrete Mathematics & Grapg Theory 3
Examples

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

[Link] a tree T has 3 vertices of degree 2, 2 vertices of 2. If a tree T has four vertices of degree 2, one vertex of
degree 3 and 2 vertices of degree 4. Find the number of degree 3, two vertices of degree 4, one vertex of degree
pendant vertices in T. 5. Find the number of leaves in T.
Solution: Solution:
Let N be the number of pendant vertices in T. Let N be the number of pendant vertices in T.
The total number of vertices in the tree The total number of vertices in the tree
T=N+3+2+2=N+7 T=N+4+1+2+1=N+8
Therefore the number of edges in the tree Therefore the number of edges in the tree T = N + 8 – 1 = N + 7
T=N+7–1=N+6 By handshaking property sum of all the degrees of the vertices: (By
𝑝
By handshaking property sum of all the degrees of the vertices: handshaking lemma σ𝑖=1 𝑑𝑒𝑔( 𝑣𝑖 ) = 2𝑞)
𝑝
(By handshaking lemma σ𝑖=1 𝑑𝑒𝑔 ( 𝑣𝑖 ) = 2𝑞) (N × 1) + (4 × 2) + (1 × 3) + (2 × 4) + (1 × 5) = 2(N + 7)
(N ×1) + (3 × 2) + (2 × 3) + (2 × 4) = 2(N + 6) N + 8 + 3 + 8 + 5 = 2N + 14
N + 6 + 6 + 8 = 2N + 12 2N – N = 24 – 14
2N – N = 20 – 12 N = 10.
N = 8.
11-04-2023 Discrete Mathematics & Grapg Theory 4
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
3. Suppose that a tree T has two vertices of degree 2, four vertices of degree 3 and three vertices of degree.
Find the number of pendant vertices in T.
Solution:

Let N be the number of pendant vertices in T.

The total number of vertices in the tree T = N + 2 + 4 + 3 = N + 9

Therefore the number of edges in the tree T = N + 9 – 1 = N + 8

By handshaking property sum of all the degrees of the vertices:

(By handshaking lemma σ𝑝𝑖=1 𝑑𝑒𝑔( 𝑣𝑖 ) = 2𝑞)

(N × 1) + (2 × 2) + (4 × 3) + (3 × 4) = 2(N + 8)

N + 4 + 12 + 12 = 2N + 16

2N – N = 28 – 16 , Therefor N = 12.
11-04-2023 Discrete Mathematics & Grapg Theory 5
Rooted Trees

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

A directed graph of tree T is said to be the rooted tree if
• T contains a unique vertex whose in degree is zero, and called the root,
• The in-degree of all other vertices of T is equal to one.

In a rooted tree we denote a root by ‘r’ and draw the tree down wards from upper level to lower level
so that arrows can be dropped, then the root will be at the uppermost level and all other vertices will
be at the lower level.

Not a rooted Rooted tree

tree

(b)
(a)
11-04-2023 Discrete Mathematics & Grapg Theory 6
Internal vertices

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

Vertices in a tree except pendent vertices are called as internal vertices.
r
1. n1 and n2 are at the first level, n3, n4 are at the second level, n5, n6, n7
n1 n2
are at the third level and n8, n9 are at the fourth level.
n3
2. n1 is the ancestor of n3, n5, n6, -n2 is the ancestor of n4, n7, n8, n9. n4
n6
n5
3. n1 is the parent of n3. n7

4. n5 and n6 are siblings and n8 and n9 are siblings . n8 n9

5. n5 , n6 , n8 and n9 are leaves and other vertices are internal vertices .

11-04-2023 Discrete Mathematics & Grapg Theory 7

 m–ary tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

• A rooted tree T is said to be m-ary tree if the out-degree of the every internal vertex of T is less than or equal
to m. A rooted tree T is said to be complete m-ary tree if the out degree of the every internal vertex of T is
exactly m.

Binary Tree
• A rooted tree T is said to be binary tree if the out-degree of internal vertices of T is less than or equal to 2.
Balanced Tree
• A rooted tree T of height h is said to be balanced tree if the level number of the leaf is h or h-1.
Complete Binary Tree
• A rooted tree T is said to be complete binary tree if the out-degree of internal vertices of T is equal to 2.
11-04-2023 Discrete Mathematics & Grapg Theory 8
Full binary Tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

A rooted tree T is called full balanced tree if all the leaves in the tree are at the same level

Note:
Let T be a complete m-ary tree of order n with p leaves and q internal vertices then we have
𝑚𝑝−1
a) 𝑛 = 𝑚𝑞 + 1 =
𝑚−1
𝑚−1 𝑛+1
b) 𝑝 = 𝑚 − 1 𝑞 + 1 =
𝑚
𝑛−1 𝑝−1
c) 𝑞 = =
𝑚 𝑚−1
11-04-2023 Discrete Mathematics & Grapg Theory 9
Examples

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

1. Find the number of vertices and the number of 2. A class room has 25 micro computers that has to
be connected to a wall socket that has four outlets.
leaves in a complete binary tree having 10 internal
The connections are made by using extension cords
vertices. that have four outlets each. What is the least number
of cords needed to get computer to use.
Solution: Solution:
Given q = 10, Here 𝑝 = 25, 𝑚 = 4, 𝑞 = ?
𝑝−1
𝑚= 2, 𝑛 = ?, 𝑞 = 𝑚−1
𝑝 =? 25−1
𝑞=
𝑛 = 𝑚𝑞 + 1 4−1
24
𝑛 = 2 × 10 + 1 𝑞= 3
= 21 𝑞=8
𝑝 = 𝑚−1 𝑞+1
Therefore the number of cords required are = 8 – 1 = 7.
= (2 – 1)10 + 1
= 11.
11-04-2023 Discrete Mathematics & Grapg Theory 10
3. A computer laboratory of a school has 10 computers that are to be connected to the wall socket that has

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

two outlets. The connections are made by using extension cords that have two outlets each. Find the least
number of cords needed to get these computer setup for use.
Solution:
Here p = 10, m = 2, q = ?

𝑞=9
Therefore the number of cords required are = 9 – 1 = 8.

11-04-2023 Discrete Mathematics & Grapg Theory 11

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
Sorting

▪ Suppose we wish to sort (rearrange/reorganise) a given list of n integers in non decreasing order.

▪ The most common (and the easiest) way of carrying out this sorting consists of two parts.

▪ In the first part, we recursively split the given list and all subsequent lists in half (or as close as

possible to half) until each sublist contains a single element.

▪ In the second part, we merge the sublists in increasing order until the original n integers have been

sorted.

▪ The splitting and merging process is done by the use of balanced complete tree.

▪ This method of sorting a list is known as Merge sort.

11-04-2023 Discrete Mathematics & Grapg Theory 12

Example

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

1. Using the merge sorting method sort the list {12, 11, 2, 3, 1, 5, 6,
{12, 11, 2, 3, 1, 5}
7, 10, 9, 4, 15}
{6, 7, 10, 9, 4, 15}

Solution: {12, 11, 2} {3, 1, 5} {6, 7, 10} {9, 4, 15}

In the first part, we recursively split the given list and all ▪ Now we merge the sublists in increasing order
subsequent lists in half (or as close as possible to half) until{12,
the11}
original
{2} {3,n 1}
integers have
{5} {6, been{9,sorted.
7} {10} 4} {15}
until each sublist contains a single element
{12, 11, 2, 3, 1, 5, 6, 7, 10, 9, 4, 15} {12} {11} {3} {1} {6} {7} {9} {4}

{12, 11, 2, 3, 1, 5} {6, 7, 10, 9, 4, 15} {11, 12} {2} {1, 3} {5} {6, 7} {10} {4, 9} {15}

{12, 11, 2} {3, 1, 5} {6, 7, 10} {9, 4, 15} {2, 11, 12} {1, 3, 5} {6, 7, 10} {4, 9, 15}

{12, 11} {2} {3, 1} {5} {6, 7} {10} {9, 4} {15} {1, 2, 3, 5, 11, 12} {4, 6, 7, 9, 10, 15}

{12} {11} {3} {1} {6} {7} {9} {4} {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 15}

{11, 12} {2} {1, 3} {5} {6, 7} {10} {4, 9} {15}

11-04-2023 Discrete Mathematics & Grapg Theory 13
 {-1, 0, 2, -2, 3} {6, -3, 5, 1, 4}

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

2. Using the merge sorting method sort the following list -1, 0, 2, -2, 3, 6, -3, 5, 1, 4
{-1, 0, 2} {-2, 3} {6, -3, 5} {1, 4}

Solution:
{-1, 0} {2} {-2} {3} {6, -3} {5} {1} {4}

{-1, 0, 2, -2, 3, 6, -3, 5, 1, 4} {-1} {0} {-2} {3} {6} {-3} {1} {4}

{-1, 0, 2, -2, 3} {6, -3, 5, 1, 4} {-1, 0} {2} {-2, 3} {-3, 6} {5} {1, 4}

{-1, 0, 2} {-2, 3} {6, -3, 5} {1, 4} {-1, 0, 2} {-2, 3} {-3, 5, 6} {1, 4}

{-1, 0} {2} {-2} {3} {6, -3} {5} {1} {4} {-2, -1, 0, 2, 3} {-3, 1, 4, 5, 6}

{-1} {0} {-2} {3} {6} {-3} {1} {4} {-3, -2, -1, 0, 1, 2, 3, 4, 5, 6}

{-1, 0} {2} {-2, 3} {-3, 6} {5} {1, 4}

{-1, 0, 2} {-2, 3} {-3, 5, 6} {1, 4}

11-04-2023 Discrete Mathematics & Grapg Theory 14

{-2, -1, 0, 2, 3} {-3, 1, 4, 5, 6}
Prefix codes and weighed trees

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

• A sequence is a set whose elements are listed in order as the 1st element, 2nd element, 3rd element, and so on.

• A sequence with only 0 and 1 is called a binary sequence or binary string.

01, 001, 101, 11001, 1000100

• Binary sequences are used as codes of message transmitting. For a message consisting the letters a, e, n, r, t
is to be transmitted. Then coding scheme:
a : 1, e : 0, n : 10, r : 01, t = 101

• Suppose with the above code, the message ‘eat’ should be transmitted. Then the code will be 01101. which
is wrong, as it also reads as rt, rar, or eaar.

• If the following code is used a : 10, e : 0, n : 1101, r : 111, t = 1100, then the message ‘eat’ is transmitted to
sequence 0101100. Which is correct.

11-04-2023 Discrete Mathematics & Grapg Theory 15

Prefix codes

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

A set P of binary sequence is called prefix code if no sequence in P is the prefix of any other sequence
in P.
Consider prefix code P2 = {000, 001, 01, 10, 11}
For example, the sets
• Longest sequence length is 3.
P1 = {10, 0, 1101, 1110, 1100}
• Construct the full binary tree of height 3, assign symbol 0 to edges
P2 = {000, 001, 01, 10, 11} directed left to child from parent, and 1 to edges directed right to child
are prefix codes, from parent.
where as the sets • 5 sequences can be 5 vertices.
A1 = {01, 0, 101, 10, 1}
A2 = {1, 00, 01, 000, 0001}
are not prefix codes.

11-04-2023 Discrete Mathematics & Grapg Theory 16

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
Example Example
Consider the prefix codes Obtain the prefix code represented by the following labeled complete
a : 111, b : 0, c : 1100, d : 1101, e : 10 binary sequence.
using these codes decode the following
sequences
(i) 1001111101
(ii) 1101111110010
(iii) 10111100110001101
Solution: Solution:
(i) e b a d Leaf: a b c d e
(ii) d a c e Sequence: 000 001 01 10 11
(iii) e a e b c b d Prefix code: P ={000, 001, 01, 10,11}

11-04-2023 Discrete Mathematics & Grapg Theory 17

Weighted Tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

▪ Consider a set of n positive integers w1, w2, w3, …..wn where 𝑤1 ≤ 𝑤2 ≤ 𝑤3 ≤ 𝑤4 ≤ . . ≤ 𝑤𝑛.
▪ Suppose we assign these integers to the n leaves of a complete binary tree T = (V, E) in any one-to-one
manner.
▪ The resulting tree is called a complete weighted, binary tree with w1, w2, w3, …..wn as weights.
▪ If l(wi) is the level number of the leaf of T to which the weight wi is assigned, then W(T) defined by
W(T) = σ𝒏𝒊=𝟏 𝒘𝒊𝒍 𝒘𝒊 is called the weight of the tree T.

Example: Find weight of the following tree T

Solution:
r
Given set of integers is {2, 4, 6, 7, 8}
𝑊(𝑇) = (2 × 3) + (4 × 3) + (6 × 2) + (7 × 2) + (8 × 2)

6 7 8
= 6 + 12 + 12 + 14 + 16
2 4
= 60

11-04-2023 Discrete Mathematics & Grapg Theory 18

Optimal Tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

Given a set of weights, suppose we consider the set of all complete binary trees to whose leaves these weights are
assigned. A tree in this set which carries the minimum weight is called an optimal tree for the weights. For a given set of
weights, there can be more than one optimal tree.
The construction of an optimal tree for a given set of weights is illustrated below.
Let (4, 15, 25, 5, 8, 16) be a set of six weights.
Let us first arrange these six weights in non-decreasing order and assign them to six isolated vertices A, B, C, D, E, F as
shown in Figure (i). The weights are indicated in brackets.

We note that the vertices A and B carry the smallest weights, 4 and 5. Add these weights to get the weight 9 and assign it
to a new vertex vj. Draw a tree having v1 as the root and A and B as its children. Rearrange the vertices present at this
stage (namely the new vertex v1 and the old vertices C, D, E, F) in the non-decreasing order of their weights. The resulting
graph is shown in Figure (ii).
11-04-2023 Discrete Mathematics & Grapg Theory 19
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
Now, among the vertices C, v1, D, E, F, two vertices which carry the smallest weights are C and v₁. Add their weights (8 and
9) to get a new weight 17. Assign this weight to a new vertex v2 and draw a tree having v2 as the root and C and v1 as its
children. Rearrange the vertices present at this stage (namely v2, D, E, F) in the non-decreasing order of their weights. The
resulting graph is shown below.

Among the vertices D, E, v2, F, the two vertices which carry minimum weights are D and E. Add their weights (15 and 16) to
get a new weight 31. Assign this weight to a new vertex v3 and draw a tree having v3 as the root and D and E as its children.
Rearrange the vertices present at this stage (namely v2, v3 and F) in the non-decreasing order of their weights. The
resulting graph is shown below.
11-04-2023 Discrete Mathematics & Grapg Theory 20
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
Among the vertices v2, F, v3, the two vertices which carry smallest weights are v2 and F. Add their weights (17 and 25) and
get a new weight 42. Assign this weight to a new vertex V4 and draw a tree having v4 as the root and v2 and F as its children.
Rearrange the vertices v3 and v4 in the non-decreasing order of their weights. The resulting graph is shown below

The disconnected graph shown above consists of two trees having v3 and v4 as roots. Add their weights (31 and 42) and get
a new weight 73. Assign this weight to a new vertex r and draw a tree having r as the root and v3 and v4 as its children. Thi s
tree is shown in Figure (vi).
11-04-2023 Discrete Mathematics & Grapg Theory 21
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
The tree obtained as explained above (that is the tree shown in Figure (vi)) is a complete, weighted binary tree whose
leaves are the vertices A, B, C, D, E, F with which we started. This tree serves as an optimal tree for the weights considered.
Keeping the weights of A, B, C, D, E, F in mind and noting their levels in the above tree, we find that the weight of the
optimal tree is
W(T) = (4×4)+(5x4) + (8 x 3) + (15 x 2) + (16 x 2) + (25 x 2) = 172

The procedure adopted in constructing an optimal tree as illustrated above is known as Huffman's procedure. The tree
itself is often called an Huffman's tree. This tree is not unique

11-04-2023 Discrete Mathematics & Grapg Theory 22

Optimal Prefix Code:

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

Huffman tree (optimal tree) can be used to obtain a prefix code for the symbols representing its leaves. For this purpose,
we first label symbols 0 and 1 to its edges by the labelling procedure indicated earlier. Then all the vertices and the leaves
of the tree can be identified by binary sequences. The binary sequences through which the leaves are identified yield a
prefix code for the symbols representing these leaves. This prefix code is known as an optimal prefix code. For example, let
us consider the Huffman tree of Figure (vi) and assign the symbols 0 and 1 to its edges according to the usual labelling rule.
The resulting labelled tree is shown Optimal Prefix Code below:

The leaves of the above tree and the binary sequences that identify these leaves are shown
in the following Table:
Leaf: A B C D E F
Binary sequence: 1010 1011 100 00 01 11
This Table displays an optimal prefix code for the symbols A, B, C, D, E, F. Since the optimal
tree is not unique, the optimal prefix code is also not unique.

11-04-2023 Discrete Mathematics & Grapg Theory 23

EXAMPLE 1: Construct an optimal prefix code for the symbols a, o, q, u, y, z that occur with frequencies 20, 28, 4, 17, 12, 7,

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

respectively.

Solution: Treating the given frequencies as the weights and the corresponding symbols as the isolated vertices, we first
arrange the symbols such that their frequencies are in nondecreasing order. This is shown below:

Now, we construct an optimal tree having q, z, y, u, a, o as leaves by using the Huffman's procedure. The construction is
done step-by-step and the graphs obtained in these steps are shown below in the order of their occurrence. (See Figures
(ii)-(vi)). The final graph is labelled (using the labelling procedure) and depicted in Figure 3.49.

11-04-2023 Discrete Mathematics & Grapg Theory 24

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
The tree shown in Figure 3.49 is an Huffmann tree (optimal tree) for the given data. From this graph, we obtain the
following optimal prefix code for the given symbols:

a: 01, 0:11, q: 1000, u: 00, y: 101, z: 1001.

11-04-2023 Discrete Mathematics & Grapg Theory 25

Example 2: Obtain an optimal prefix code for the message ROAD IS GOOD. Indicate the code.

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

► The given message consists of letters R, O, A, D, I, S, G with frequencies 1, 3, 1, 2, 1, 1, 1, respectively. Further, there is a
blank space (□) occurring twice (- one between ROAD and IS, and another between IS and GOOD).First, we arrange the
letters and in the non-decreasing order of their weights (frequencies). Their representation as isolated vertices is shown
below:

We now construct an optimal tree having these symbols as leaves by using the Huffman procedure. The graphs obtained in
successive steps of the procedure are shown below in Figures (ii)-(viii) in the order of their occurrence. The labelled version
of the final trees hown in Figure (viii)

11-04-2023 Discrete Mathematics & Grapg Theory 26

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
The tree shown in Figure (viii) is the optimal tree that we sought. From this tree, we obtain the following optional prefix
code for the symbols with which we started. R: 1110, A: 1111, I: 000, S: 001,G: 100, : 101, D: 110 0:01 Accordingly, the
code for the given message ROAD IS GOOD is 11100111111101010000011011000101110
11-04-2023 Discrete Mathematics & Grapg Theory 27
EXAMPLE 3: Obtain an optimal prefix code for the message LETTER RECEIVED. Indicate the code.

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

►The given message consists of letters L, E, T, R, C, I, V, D with frequencies 1, 5, 2, 2, 1, 1, 1, 1 respectively. Further, there is
one blank space (□) between the two words of the message. First, we arrange the letters and in the non-decreasing order of
their weights (frequencies). Their representation as isolated vertices is shown below

11-04-2023 Discrete Mathematics & Grapg Theory 28

Spanning Trees

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

• A subgraph T of a graph G is called a spanning tree when T is a tree and contains all vertices of G.

• Every connected graph has a spanning tree, any two spanning trees have the same number of edges.

• Spanning tree is also called maximal tree.

• Edges of a spanning tree is called branches.

• A weighted graph is a graph in which each edge has an associated real number weight.

• A minimal spanning tree (MST) is a spanning tree with the least total weight of its edges.

Theorems

1. A graph is connected if and only if it has a spanning tree,

2. With respect to any of its spanning trees, a connected graph of n vertices and m edges has n – 1 branches and m –
n + 1 chords.
11-04-2023 Discrete Mathematics & Grapg Theory 29
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
If G has n vertices, a spanning tree of G must have n vertices and n-1 edges. If T is a spanning tree of a graph

G, then the edges of G which are not in T are called the chords of G with respect to T. The set of all chords of G

ഥ. Evidently
is the complement of T in G. This set is called the chord-set or cotree of T in G and is denoted by 𝑻
n1 n1 n1
ഥ.
G= TU𝑻

n2 n3 n2 n3 n2 n3

n4 n5 n4 n5 n4 n5

(a) : G (b) : T ഥ
(c) : 𝐓

Note:-The Graph G = (V, E) is an undirected graph then G is connected if and only if G has a spanning tree.
11-04-2023 Discrete Mathematics & Grapg Theory 30
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
1. Find the spanning trees of the graph. 2. Find the spanning trees of the graph. Find all the non-
isomorphic spanning trees of the graph G.

Solution
Solution

Non isomorphic trees

11-04-2023 Discrete Mathematics & Grapg Theory 31

 3
Minimal Spanning Tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

• In graph G there is a positive real number at each 5 3 4
1
edge then G is called weighted Graph, and the
positive number is called weight. 2
• Let us consider a weighted graph G, let T be a This graph has three spanning tree as given below
3 3
spanning tree of G. Then every branch of T is an
edge in G.
1 5 3 4 1 3 4
• The sum of the weights of all the branches of T is
called the weight of T. 2
• Weight of an edge e of G is denoted by wt(e) and
3
weight of spanning tree T of G is denoted by wt(t).
• A spanning tree whose weight is the least is called 1 5 4
minimal spanning tree of the graph.

11-04-2023 Discrete Mathematics & Grapg Theory 32

Algorithms for Minimal Spanning Tree

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

There are several methods of constructing minimal spanning trees. The first of these is Kruskal and second is Prim algorithm.

Kruskal Algorithm:
The working rule for the Kruskal’s method (usually called Kruskal’s algorithm) may be stated as follows
➢ Step1: Given a connected, weighted graph G with n vertices, list the edges of G in the order of nondecreasing weights.
➢ Step2: Starting with a smallest weighted edge, proceed sequentially by selecting one edge at a time such that no cycle is
formed.
➢ Step3: Stop the process of step2 when (n-1) edges are selected. These (n-1) edges constitute a minimal spanning tree of G.

Remarks
➢ If two or more edges have the same weight, there will be more than one listing of edges in non-decreasing order of
weights. Different listing may yield different minimal spanning trees. As such, Kruskal algorithm does not determine a
unique minimal spanning tree.
➢ The process in step2 is called Greedy Process.
11-04-2023 Discrete Mathematics & Grapg Theory 33
Example
Using Kruskal’s Algorithm, find a minimal spanning tree for the given weighted graph

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

Solution
We observe that the given graph has 6 vertices; hence a spanning tree there of will have 5 edges (branches).
Let us put the graph in a non decreasing order of their weights and successively select 5 edges such a way that no cycle is
created. This scheme is summarized in the following table
Edge CR PR QR BQ BR AB BC AQ PQ
Weight 5 7 7 8 9 10 10 11 12
Select? YES YES YES YES NO YES

Thus, a minimal spanning tree of the given graph contains the five edges CR, PR,
QR, BQ, AB. This tree is shown in the figure. The weight of the tree is 37 units.
11-04-2023 Discrete Mathematics & Grapg Theory 34
Example
Using Kruskal’s Algorithm, find a minimal spanning tree for the given weighted graph

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

11-04-2023 Discrete Mathematics & Grapg Theory 35
Prim’s Algorithm:
The working rule for the Prim’s Method(Usually called Prim’s algorithm) may be stated as follows

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

➢ Step1: Given a connected, weighted graph G with n vertices, Assign n names (say v1,v2,…,vn or A, B, C, and so on) to
these vertices, and prepare a n x n table in which the weights of all edges are shown. The entries in the table will be
symmetric with respect to the diagonal and no entries appear on the diagonal, indicate the weights of the non existing edges
as ∞.
➢ Step2: Start from vertex v1 (or A, as the case may be) and connect it to its nearest neighbour (i.e., to the vertex has the
smallest entry) in the v1 row, say vk. Now, consider the edge {v1, vk} and connect it to its closest neighbour (i.e., to a vertex,
other than v1 and vk, that has the smallest entry among all entries in v1 and vk rows). Let this be vm.
➢ Step3: Start from the vertex vm and repeat the process of step2. stop the process when all the n vertices have been
connected by n-1 edges. These n-1 edges constitute a minimal spanning tree.
Remarks
➢ In the process of connected an edge to its nearest neighbour as explained above, care has to be taken that cycle are not
created by the connections.
➢ Like in the Kruskal’s method, a minimal spanning tree determined by the prims method is not unique.

11-04-2023 Discrete Mathematics & Grapg Theory 36

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
1. Using Prim algorithm find a minimal spanning tree for the given
weighted graph.

Solution
We observe that the graph has 5 vertices. Therefore the minimal spanning tree there of will have 4 edges. Let us tabulate the
weights of the edges between every pair of vertices as shown below
v1 v2 v3 v4 v5
v1 - 4 ∞ ∞ 5
v2 4 - 3 6 1
v3 ∞ 3 - 6 2
v4 ∞ 6 6 - 7
v5 5 1 2 7 -

Now let us start with the first row (v1 row) and pick the smallest entry therein. This is 4 which corresponds to the edge
{v1, v2}. By examining all the entries in v1- and v2-rows, we find that the vertex other than v1 and v2 which corresponds
to smallest entry is v5 (smallest entry being 1). Thus v5 is closest to the edge {v1, v2}. Let us connect v5 to the {v1, v2} at
v2 (because {v5, v2} has smaller weight than {v5, v1}).
11-04-2023 Discrete Mathematics & Grapg Theory 37
 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
Let us now examine the v5-row and note that small entry is 1 which corresponds to the edge {v5, v2}. By examining all
entries in v2- and v5 rows, we find that the vertex other than v2 and v5 which corresponds to the smallest entry v3. thus v3
is closest to the edge {v2, v5}.

Let us connect v3 to the edge {v2, v5} at v5.

Thus the edges {v1, v2}, {v2, v5}, {v5, v3} belongs to a minimal spanning tree. The vertices left over at this stage is v4
which is joined to v2, v3, and v5 in the given graph. Among the edges that contain v4, the edges {v2, v4} and {v3, v4}
have equal minimal weights. Therefore we can include either of those edges in the minimal spanning tree.

Accordingly, the degree {v1, v2}, {v2, v5}, {v5, v3} together with the edge {v2, v4} or the edge {v3, v4} constitute a
minimal spanning tree. Thus, for the given graph, there are two minimal spanning trees as shown in the figure (a), (b). The
weight of each of these trees is 13 units.

11-04-2023 Discrete Mathematics & Grapg Theory 38

 @ Dr Vishal Patil, FET Jain (Deemed-to-be University)
2. Using Prim’s algorithm, find a minimal spanning tree of the weighted graph

Solution
We observe that the graph has 6 vertices. Therefore the minimal spanning tree thereof will have 5 edges. Let us tabulate the
weights of the edges between every pair of vertices as shown below
A B C D E F
A - 2 4 ∞ ∞ 2
B 2 - 1 ∞ 4 ∞
C 4 1 - 3 3 1
D ∞ ∞ 3 - 3 5
E ∞ 4 3 3 - 4
F 2 ∞ 1 5 4 -

11-04-2023 Discrete Mathematics & Grapg Theory 39

2. Using Prim’s algorithm, find a minimal spanning tree of the weighted graph

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)

11-04-2023 Discrete Mathematics & Grapg Theory 40
11-04-2023
Discrete Mathematics & Grapg Theory
41

@ Dr Vishal Patil, FET Jain (Deemed-to-be University)