Spanning Tree

A spanning tree of a connected undirected graph G is a tree that minimally includes all of
the vertices of G. A graph may have many spanning trees.

Example of a Spanning Tree

Let's understand the spanning tree with examples below:
Let the given graph be:

Some of the possible spanning trees that can be created

from the above graph are:

The possible spanning trees: 6

Spanning Tree Applications

 Computer Network Routing Protocol

 Cluster Analysis
 Civil Network Planning
 Minimum Spanning Tree
A spanning tree with assigned weight less than or equal to the weight of every possible
spanning tree of a weighted, connected and undirected graph G, it is called minimum
spanning tree (MST). The weight of a spanning tree is the sum of all the weights assigned to
each edge of the spanning tree.

Minimum Spanning tree Applications

 To find paths in the map
 To design networks like telecommunication networks, water supply networks, and
electrical grids.
The minimum spanning tree from a graph is found using the following algorithms:
1. Kruskal's Algorithm
2. Prim's Algorithm

1.Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a
connected weighted graph. It finds a tree of that graph which includes every vertex and the
total weight of all the edges in the tree is less than or equal to every possible spanning tree.

Algorithm
Step 1 − Arrange all the edges of the given graph G(V,E) in ascending order as per their
edge weight.
Step 2 − Choose the smallest weighted edge from the graph and check if it forms a cycle
with the spanning tree formed so far.
Step 3 − If there is no cycle, include this edge to the spanning tree else discard it.
Step 4 − Repeat Step 2 and Step 3 until (V−1) number of edges are left in the spanning tree.
Problem
Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s
algorithm.

Solution

From the above graph we construct the following table −

Edge
Edge No. Vertex Pair
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
Now we will rearrange the table in ascending order with respect to Edge weight −
Edge Vertex Edge
No. Pair 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
Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal
spanning tree and its total weight is (1+2+3+5+9)=20.

Prim's Algorithm
Prim's algorithm, discovered in 1930 by mathematicians, Vojtech Jarnik and Robert C.
Prim, is a greedy algorithm that finds a minimum spanning tree for a connected weighted
graph. It finds a tree of that graph which includes every vertex and the total weight of all
the edges in the tree is less than or equal to every possible spanning tree. Prim’s algorithm
is faster on dense graphs.

Algorithm
 Initialize the minimal spanning tree with a single vertex, randomly chosen from the
graph.
 Repeat steps 3 and 4 until all the vertices are included in 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.
 Add the selected edge and the vertex that it connects to the tree.

Problem
Suppose we want to find minimum spanning tree for the following graph G using Prim’s
algorithm.
Graph Coloring
Graph coloring is the procedure of assignment of colors to each vertex of a graph G such
that no adjacent vertices get same color. The objective is to minimize the number of colors
while coloring a graph. The smallest number of colors required to color a graph G is called
its chromatic number of that graph. Graph coloring problem is a NP Complete problem.

Method to Color a Graph

The steps required to color a graph G with n number of vertices are as follows −
Step 1 − Arrange the vertices of the graph in some order.
Step 2 − Choose the first vertex and color it with the first color.
Step 3 − Choose the next vertex and color it with the lowest numbered color that has not
been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this
color, assign a new color to it. Repeat this step until all the vertices are colored.

example

In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are
again adjacent, vertex b and vertex d are colored with different color, green and blue
respectively. Then vertex c is colored as red as no adjacent vertex of c is colored red. Hence,
we could color the graph by 3 colors. Hence, the chromatic number of the graph is 3.

Applications of Graph Coloring

Some applications of graph coloring include −
 Register Allocation
 Map Coloring
 Bipartite Graph Checking
 Mobile Radio Frequency Assignment
 Making time table, etc.

Chromatic Number
The chromatic number can be described as the minimum number of colors required
to properly color any graph. In other words, the chromatic number can be described
as a minimum number of colors that are needed to color any graph in such a way
that no two adjacent vertices of a graph will be assigned the same color.

Example of Chromatic number:

To understand the chromatic number, we will consider a graph, which is
described as follows:

The above graph contains some points, which are described as follows:
o The same color is not used to color the two adjacent vertices.
o The minimum number of colors of this graph is 3, which is needed to properly
color the vertices.
o Hence, in this graph, the chromatic number = 3
o If we want to properly color this graph, in this case, we are required at least 3
colors.

Types of Chromatic Number of Graphs:

There are various types of chromatic number of graphs, which are described
as follows:
Cycle Graph:
A graph will be known as a cycle graph if it contains 'n' edges and 'n' vertices
(n >= 3), which form a cycle of length 'n'. There can be only 2 or 3 number
of degrees of all the vertices in the cycle graph.
Chromatic number:
1. The chromatic number in a cycle graph will be 2 if the number of
vertices in that graph is even.
2. The chromatic number in a cycle graph will be 3 if the number of
vertices in that graph is odd.
Examples of Cycle graph:
There are various examples of cycle graphs. Some of them are described as
follows:
Example 1: In the following graph, we have to determine the chromatic
number.

Solution: In the above cycle graph, there are 3 different colors for
three vertices, and none of the adjacent vertices are colored with the same color. In
this graph, the number of vertices is odd. So Chromatic number = 3

Planner Graph
A graph will be known as a planner graph if it is drawn in a plane. The edges
of the planner graph must not cross each other.
Chromatic Number:
1. In a planner graph, the chromatic Number must be Less than or equal
to 4.
2. The planner graph can also be shown by all the above cycle graphs
except example 3.
Examples of Planer graph:
There are various examples of planer graphs. Some of them are
described as follows:
Example 1: In the following graph, we have to determine the chromatic
number.

Solution: In the above graph, there are 3 different colors for three vertices,
and none of the edges of this graph cross each other. So
Chromatic number = 3
Here, the chromatic number is less than 4, so this graph is a plane graph.
Bipartite Graph
A graph will be known as a bipartite graph if it contains two sets of vertices,
A and B. The vertex of A can only join with the vertices of B. That means the
edges cannot join the vertices with a set.
Chromatic Number
In any bipartite graph, the chromatic number is always equal to 2.
Examples of Bipartite graph:
There are various examples of bipartite graphs. Some of them are described
as follows:
Example 1: In the following graph, we have to determine the chromatic
number.

Solution: There are 2 different sets of vertices in the above graph. So

the chromatic number of all bipartite graphs will always be 2. So
Chromatic number = 2
Tree:
A connected graph will be known as a tree if there are no circuits in that
graph. In a tree, the chromatic number will equal to 2 no matter how many
vertices are in the tree. Every bipartite graph is also a tree.

Chromatic Number
In any tree, the chromatic number is equal to 2.
Examples of Tree:
There are various examples of a tree. Some of them are described as follows:
Example 1: In the following tree, we have to determine the chromatic
number.

Solution: There are 2 different colors for four vertices. A tree with any
number of vertices must contain the chromatic number as 2 in the above
tree. So,
Chromatic number = 2
Example 2: In the following tree, we have to determine the chromatic
number.

Solution: There are 2 different colors for five vertices. A tree with any
number of vertices must contain the chromatic number as 2 in the above
tree. So,
Chromatic number = 2
Graph Traversal

Graph traversal is the problem of visiting all the vertices of a graph in some systematic
order. There are mainly two ways to traverse a graph.

 Breadth First Search

 Depth First Search

Breadth First Search

Breadth First Search (BFS) starts at starting level-0 vertex X of the graph G. Then we visit
all the vertices that are the neighbors of X. After visiting, we mark the vertices as "visited,"
and place them into level-1. Then we start from the level-1 vertices and apply the same
method on every level-1 vertex and so on. The BFS traversal terminates when every vertex
of the graph has been visited.

BFS Algorithm

The concept is to visit all the neighbor vertices before visiting other neighbor vertices of
neighbor vertices.

 Initialize status of all nodes as “Ready”.

 Put source vertex in a queue and change its status to “Waiting”.
 Repeat the following two steps until queue is empty −
o Remove the first vertex from the queue and mark it as “Visited”.
o Add to the rear of queue all neighbors of the removed vertex whose status is
“Ready”. Mark their status as “Waiting”.
Graph Traversal
Graph traversal is a technique used for searching a vertex in a graph. The graph traversal is
also used to decide the order of vertices is visited in the search process. A graph traversal
finds the edges to be used in the process without creating loops. That means using graph
traversal we visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques.

1. BFS( Breadth First Search)
2. DFS(Deapth First Search)
Example:
.