Graph

What is a Graph?
Definition − A graph (denoted as G=(V, E) consists of a non-empty set of vertices or nodes V and a set of
edges E.
Example − Let us consider, a Graph is G=(V,E) where V={a,b,c,d} and E={{a,b},{a,c},{b,c},{c,d}}

Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number of edges
incident with the vertex V.

Vertex Degree Even / Odd

a 2 even

b 2 even

c 3 odd

d 1 odd

Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and if the
degree of a vertex is odd, the vertex is called an odd vertex.

Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the above graph
the degree of the graph is 3.

The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to twice the
number of edges.

Types of Graphs

There are different types of graphs, which we will learn in the following section.

Null Graph
A null graph has no edges. The null graph of n vertices is denoted by Nn

Page | 1
Simple Graph

A graph is called simple graph/strict graph if the graph is undirected and does not contain any loops or
multiple edges.

Multi-Graph

If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph. In other
words, it is a graph having at least one loop or multiple edges.

Directed and Undirected Graph

A graph G=(V,E) is called a directed graph if the edge set is made of ordered vertex pair and a graph is
called undirected if the edge set is made of unordered vertex pair.

Connected and Disconnected Graph

A graph is connected if any two vertices of the graph are connected by a path; while a graph is
disconnected if at least two vertices of the graph are not connected by a path. If a graph G is disconnected,
then every maximal connected subgraph of GG is called a connected component of the graph GG.

Page | 2
Regular Graph
A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree rr,
the degree of each vertex of GG is r.

Complete Graph
A graph is called complete graph if every two vertices pair are joined by exactly one edge. The complete
graph with n vertices is denoted by Kn

Cycle Graph
If a graph consists of a single cycle, it is called cycle graph. The cycle graph with n vertices is denoted
by Cn

Bipartite Graph
If the vertex-set of a graph G can be split into two disjoint sets, V1 and V2, in such a way that each edge in
the graph joins a vertex in V1 to a vertex in V2, and there are no edges in G that connect two vertices
in V1 or two vertices in V2, then the graph GG is called a bipartite graph.

Page | 3
Complete Bipartite Graph
A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every
single vertex in the second set. The complete bipartite graph is denoted by Kx,y where the
graph GG contains xx vertices in the first set and y vertices in the second set.

Representation of Graphs

There are mainly two ways to represent a graph −

 Adjacency Matrix
 Adjacency List
Adjacency Matrix
An Adjacency Matrix A[V][V] is a 2D array of size V×V where V is the number of vertices in a undirected
graph. If there is an edge between Vx to Vy then the value of A[Vx][Vy]= 1 and A[Vy][Vx]=, otherwise the
value will be zero. And for a directed graph, if there is an edge between Vx to Vy, then the value
of A[Vx][Vy]=, otherwise the value will be zero.

Adjacency Matrix of an Undirected Graph

Let us consider the following undirected graph and construct the adjacency matrix −

Page | 4
Adjacency matrix of the above undirected graph will be −

a b c d

a 0 1 1 0

b 1 0 1 0

c 1 1 0 1

d 0 0 1 0

Adjacency Matrix of a Directed Graph

Let us consider the following directed graph and construct its adjacency matrix −

Adjacency matrix of the above directed graph will be −

a b c d

a 0 1 1 0

Page | 5
 b 0 0 1 0

c 0 0 0 1

d 0 0 0 0

Adjacency List
In adjacency list, an array (A[V]) of linked lists is used to represent the graph G with VV number of
vertices. An entry A[Vx] represents the linked list of vertices adjacent to the Vx−th vertex. The adjacency
list of the undirected graph is as shown in the figure below −

Planar vs. Non-planar graph

Planar graph − A graph GG is called a planar graph if it can be drawn in a plane without any edges
crossed. If we draw graph in the plane without edge crossing, it is called embedding the graph in the
plane.

Non-planar graph − A graph is non-planar if it cannot be drawn in a plane without graph edges crossing.

Page | 6
Isomorphism
If two graphs G and H contain the same number of vertices connected in the same way, they are called
isomorphic graphs (denoted by G≅H).

It is easier to check non-isomorphism than isomorphism. If any of these following conditions occurs, then
two graphs are non-isomorphic −

 The number of connected components are different

 Vertex-set cardinalities are different
 Edge-set cardinalities are different
 Degree sequences are different
Example

The following graphs are isomorphic −

Homomorphism
A homomorphism from a graph GG to a graph HH is a mapping (May not be a bijective
mapping)h:G→H such that − (x,y)∈E(G)→(h(x),h(y))∈E(H). It maps adjacent vertices of graph G to the
adjacent vertices of the graph H.
Properties of Homomorphisms
 A homomorphism is an isomorphism if it is a bijective mapping.
 Homomorphism always preserves edges and connectedness of a graph.
 The compositions of homomorphisms are also homomorphisms.
 To find out if there exists any homomorphic graph of another graph is a NPcomplete problem.

Page | 7
Euler Graphs
A connected graph G is called an Euler graph, if there is a closed trail which includes every edge of the
graph GG. An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and
ends at different vertices.
An Euler circuit is a circuit that uses every edge of a graph exactly once. A Euler circuit always starts and
ends at the same vertex. A connected graph GG is an Euler graph if and only if all vertices of GG are of
even degree, and a connected graph GG is Eulerian if and only if its edge set can be decomposed into
cycles.

The above graph is an Euler graph as “a1b2c3d4e5c6f7g”” covers all the edges of the graph.

Hamiltonian Graphs
A connected graph G is called Hamiltonian graph if there is a cycle which includes every vertex of G and
the cycle is called Hamiltonian cycle. Hamiltonian walk in graph GG is a walk that passes through each
vertex exactly once.
If G is a simple graph with n vertices, where n≥3 If deg(v)≥n for each vertex v, then the graph G is
Hamiltonian graph. This is called Dirac's Theorem.
If G is a simple graph with n vertices, where n≥2n≥2 if deg(x)+deg(y)≥n for each pair of non-adjacent
vertices x and y, then the graph G is Hamiltonian graph. This is called Ore's theorem.

Page | 8
Example 1. Consider the graph G in Figure 9.2. The vertex 12 is an isolated vertex whereas the vertex 10
is a pendant vertex. We have N(1) = f2; 4; 7g, d(1) = 3. The vertices 1 and 6 are not adjacent. The set f9; 10;
11; 2; 4; 7g is an independent vertex set. The set f1; 2g; f8; 10g; f4; 5g is an independent edge set

Definition: Let G = (V; E) be a graph on n vertices, say V = f1; : : : ; ng. Then, G is said to
be a:

Page | 9
Introduction to Tree
A tree is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate
and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship
between the nodes.
The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node
can have multiple child nodes, and these child nodes can also have their own child nodes, forming a
recursive structure

Page | 10
Tree and its Properties

Definition − A Tree is a connected acyclic undirected graph. There is a unique path between every pair of
vertices in G. A tree with N number of vertices contains (N−1) number of edges. The vertex which is of 0
degree is called root of the tree. The vertex which is of 1 degree is called leaf node of the tree and the degree
of an internal node is at least 2.

Example − The following is an example of a tree −

Binary Trees:

Page | 11
If the outdegree of every node is less than or equal to 2, in a directed tree than the tree is called a binary
tree. A tree consisting of the nodes (empty tree) is also a binary tree. A binary tree is shown in fig:

Basic Terminology:

Root: A binary tree has a unique node called the root of the tree.

Left Child: The node to the left of the root is called its left child.

Right Child: The node to the right of the root is called its right child.

Parent: A node having a left child or right child or both are called the parent of the nodes.

Siblings: Two nodes having the same parent are called siblings.

Leaf: A node with no children is called a leaf. The number of leaves in a binary tree can vary from one
(minimum) to half the number of vertices (maximum) in a tree.

Descendant: A node is called descendant of another node if it is the child of the node or child of some other
descendant of that node. All the nodes in the tree are descendants of the root.

Left Subtree: The subtree whose root is the left child of some node is called the left subtree of that node.

Example: For the tree as shown in fig:

Page | 12
 o Which node is the root?

o Which nodes are leaves?

o Name the parent node of each node

Solution: (i) The node A is the root node.

(ii) The nodes G, H, I, L, M, N, O are leaves.
(iii) Nodes Parent
B, C A
D, E B
F C
G, H D
I, J E
K F
L, M J
N, O K

Page | 13
Right Subtree: The subtree whose root is the right child of some node is called the right subtree of that
node.

Level of a Node: The level of a node is its distance from the root. The level of root is defined as zero. The
level of all other nodes is one more than its parent node. The maximum number of nodes at any level N is
2N.

Depth or Height of a tree: The depth or height of a tree is defined as the maximum number of nodes in a
branch of a tree. This is more than the maximum level of the tree, i.e., the depth of root is one. The
maximum number of nodes in a binary tree of depth d is 2d-1, where d ≥1.

External Nodes: The nodes which have no children are called external nodes or terminal nodes.

Internal Nodes: The nodes which have one or more than one children are called internal nodes or non-
terminal nodes.

Binary Expression Trees:

An algebraic expression can be conveniently expressed by its expression tree. An expression having
binary operators can be decomposed into
<left operand or expression> (operator) <right operand or expression>
Example: Construct the binary expression tree for the expression (a+b)*(d/c)

Solution: The binary expression tree for the expression (a+b)*(d/c) is shown in fig:

Page | 14
Differentiate between General Tree and Binary Tree

General Tree Binary Tree

1. There is no such tree having zero nodes or 1. There may be an empty binary tree.
an empty general tree.

2. If some node has a child, then there is no 2. If some node has a child, then it is distinguished as a left child or
such distinction. a right child.

3. The trees shown in fig are the same, when 3. The trees shown in fig are distinct, when we consider them as
we consider them as general trees. binary trees, because in (4) is the right child of 2 while in (ii) 4 is a
left child of 2.

Page | 15
Traversing Binary Trees
Traversing means to visit all the nodes of the tree. There are three standard methods to traverse the binary
trees. These are as follows:

1. Preorder Traversal

2. Postorder Traversal

3. Inorder Traversal

1. Preorder Traversal: The preorder traversal of a binary tree is a recursive process. The preorder
traversal of a tree is

o Visit the root of the tree.

o Traverse the left subtree in preorder.

o Traverse the right subtree in preorder.

2. Postorder Traversal: The postorder traversal of a binary tree is a recursive process. The postorder
traversal of a tree is

o Traverse the left subtree in postorder.

o Traverse the right subtree in postorder.

o Visit the root of the tree.

3. Inorder Traversal: The inorder traversal of a binary tree is a recursive process. The inorder traversal
of a tree is

o Traverse in inorder the left subtree.

o Visit the root of the tree.

o Traverse in inorder the right subtree.

Example: Determine the preorder, postorder and inorder traversal of the binary tree as shown in fig:

Page | 16
Solution: The preorder, postorder and inorder traversal of the tree is as follows:

Preorder 1 2 3 4 5 6 7 8 9 10 11

Postorder 3 5 4 2 7 10 9 11 8 6 1

Inorder 3 2 5 4 1 7 6 9 10 8 11

Algorithms:

(a)Algorithm to draw a Unique Binary Tree when Inorder and Preorder Traversal of the tree is
Given:

1. We know that the root of the binary tree is the first node in its preorder. Draw the root of the tree.

2. To find the left child of the root node, first, use the inorder traversal to find the nodes in the left subtree of
the binary tree. (All the nodes that are left to the root node in the inorder traversal are the nodes of the left
subtree). After that, the left child of the root is obtained by selecting the first node in the preorder traversal
of the left subtree. Draw the left child.

Page | 17
 3. In the same way, use the inorder traversal to find the nodes in the right subtree of the binary tree. Then the
right child is obtained by selecting the first node in the preorder traversal of the right subtree. Draw the right
child.

4. Repeat the steps 2 and 3 with each new node until every node is not visited in the preorder. Finally, we obtain
a unique tree.

Example: Draw the unique binary tree when the inorder and preorder traversal is given as follows:

Inorder B A D C F E J H K G I

Preorder A B C D E F G H J K I

Solution: We know that the root of the binary tree is the first node in preorder traversal. Now, check A, in
the inorder traversal, all the nodes that are of left A, are nodes of left subtree and all the nodes that are
right of A, are nodes of right subtree. Read the next node in the preorder and check its position against the
root node, if its left of the root node, then draw it as a left child, otherwise draw it a right child. Repeat the
above process for each new node until all the nodes of the preorder traversal are read and finally we obtain
the binary tree as shown in fig:

(b) Algorithm to draw a Unique Binary Tree when Inorder and Postorder Traversal of the tree is
Given:

Page | 18
 1. We know that the root of the binary tree is the last node in its postorder. Draw the root of the tree.

2. To find the right child of the root node, first, use the inorder traversal to find the nodes in the right subtree
of the binary tree. (All the nodes that are right to the root node in the inorder traversal are the nodes of the
right subtree). After that, the right child of the root is obtained by selecting the last node in the postorder
traversal of the right subtree. Draw the right child.

3. In the same way, use the inorder traversal to find the nodes in the left subtree of the binary tree. Then the
left child is obtained by selecting the last node in the postorder traversal of the left subtree. Draw the left
child.

4. Repeat the steps 2 and 3 with each new node until every node is not visited in the postorder. After visiting
the last node, we obtain a unique tree.

Example: Draw the unique binary tree for the given Inorder and Postorder traversal is given as follows:

Inorder 4 6 10 12 8 2 1 5 7 11 13 9 3

Postorder 12 10 8 6 4 2 13 11 9 7 5 3 1

Solution: We know that the root of the binary tree is the last node in the postorder traversal. Hence, one
in the root node.

Now, check the inorder traversal, we know that root is at the center, hence all the nodes that are left to the
root node in inorder traversal are the nodes of left subtree and, all that are right to the root node are the
nodes of the right subtree.

Now, visit the next node from back in postorder traversal and check its position in inorder traversal, if
it is on the left of root then draw it as left child and if it is on the right, then draw it as the right child.

Repeat the above process for each new node, and we obtain the binary tree as shown in fig:

Page | 19
(c)Algorithm to convert General Tree into the binary tree

1. Starting from the root node, the root of the tree is also the root of the binary tree.

2. The first child C1(from left) of the root node in the tree is the left child C1 of the root node in the binary tree,
and the sibling of the C1 is the right child of C1 and so on.

3. Repeat the step2 for each new node.

Example: Convert the following tree as shown in fig into a binary tree.

Page | 20
Solution: The root of the tree is the root of the binary tree. Hence A is the root of the binary tree. Now B
becomes the left child of A in a binary tree, C becomes the right child of B, D becomes right child of C, and
E becomes the right child of D in the binary tree and similarly applying the algorithm we obtain the binary
tree as shown in fig:

Page | 21
Binary Search Trees
Binary search trees have the property that the node to the left contains a smaller value than the node
pointing to it and the node to the right contains a larger value than the node pointing to it.

It is not necessary that a node in a 'Binary Search Tree' point to the nodes whose value immediately precede
and follow it.

Example: The tree shown in fig is a binary search tree.

Page | 22
Inserting into a Binary Search Tree: Consider a binary tree T. Suppose we have given an ITEM of information to
insert in T. The ITEM is inserted as a leaf in the tree. The following steps explain a procedure to insert an ITEM in the
binary search tree T

1. Compare the ITEM with the root node.

2. If ITEM>ROOT NODE, proceed to the right child, and it becomes a root node for the right subtree.

3. If ITEM<ROOT NODE, proceed to the left child.

4. Repeat the above steps until we meet a node which has no left and right subtree.

5. Now if the ITEM is greater than the node, then the ITEM is inserted as the right child, and if the ITEM
is less than the node, then the ITEM is inserted as the left child.

Example: Show the binary search tree after inserting 3, 1,4,6,9,2,5,7 into an initially empty binary search
tree.

Solution: The insertion of the above nodes in the empty binary search tree is shown in fig:

Page | 23
Deletion in a Binary Search Tree: Consider a binary tree T. Suppose we want to delete a given ITEM from
binary search tree. To delete an ITEM from a binary search tree we have three cases, depending upon the
number of children of the deleted node.

1. Deleted Node has no children: Deleting a node which has no children is very simple, as replace
the node with null.

2. Deleted Node has Only one child: Replace the value of a deleted node with the only child.

Page | 24
 3. Deletion node has only two children: In this case, replace the deleted node with the node that is
closest in the value to the deleted node. To find the nearest value, we move once to the left and then
to the right as far as possible. This node is called the immediate predecessor. Now replace the value
of the deleted node with the immediate predecessor and then delete the replaced node by using
case1 or case2.

Example: Show that the binary tree shown in fig (viii) after deleting the root node.

Solution: To delete the root node, first replace the root node with the closest elements of the root. For this,
first, move one step left and then to the right as far as possible to the [Link] delete the replaced node.
The tree after deletion shown in fig:

Discrete Mathematics - Spanning Trees

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.

Page | 25
Example

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.

Example

Page | 26
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)(�−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
Page | 27
From the above graph we construct the following table −

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

Now we will rearrange the table in ascending order with respect to Edge weight −

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

Page | 28
E1 (a, b) 20

Page | 29
Page | 30
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(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.

Page | 31
Solution

Here we start with the vertex ‘a’ and proceed.

Page | 32
Page | 33
This is the minimal spanning tree and its total weight is (1+2+3+5+9)=20(1+2+3+5+9)=20.

Page | 34