Data Structure (2130702)

BE | Semester-3   Summer-2019 | 06/04/2019

Q5) (c)

Representation of Graph

• A diagrammatic representation of a graph may have limited usefulness. However such a representation is not feasible when number of nodes an edges in a graph is large.
• Hence the graph can be represented in another two ways.
• Matrix representation of Graph
• Linked List representation of Graph

Matrix Representation of Graph (Adjacency matrix)

• It is easy to store and manipulate matrices and hence the graphs represented by them in the computer.
• Let G = (V, E) be a simple diagraph in which V = {V1, V2,…., Vn} and the nodes are assumed to be ordered from V1 to Vn.
• An n x n matrix A is called Adjacency matrix of the graph G whose elements are aij are given by.

• An element of the adjacency matrix is either 0 or 1
• Any matrix whose elements are either 0 or 1 is called bit matrix or Boolean matrix
• For a given graph G = m(V, E), an adjacency matrix depends upon the ordering of the elements of V
• For different ordering of the elements of V we get different adjacency matrices.

• The number of elements in the ith row whose value is 1 is equal to the out-degree of node Vi.
• The number of elements in the jth column whose value is 1 is equal to the in-degree of node Vj.
• For a NULL graph which consist of only n nodes but no edges, the adjacency matrix has all its elements 0. i.e. the adjacency matrix is the NULL matrix.