Representation Of Graphs

REPRESENTATION OF GRAPHS: Although a diagrammatic representation of a graph is very convenient for a visual study but this is only possible when the number of nodes and edges is reasonably small.
Two types of representation are given below :

Matrix representation: The matrix are commonly used to represent graphs for computer processing. The advantages of representing the graph in matrix form lies on the fact that many results of matrix algebra can be readily applied to study the structural properties of graphs from an algebraic point of view. There are number of matrices which one can associate witch any graph. We shall discuss adjacency matrix and the incidence matrix.

Adjacency matrix

(a) Representation of undirected graph
The adjacency matrix of a graph G with n vertices and no parallel edges is an n by n matrix A = {aij} whose elements are given by aij = 1, if there is an edge between ith and jth vertices, and = O, if there is no edge between them.

Note that for a given graph, the adjacency matrix is based on ordering chosen for the vertices.

Hence, there are as many as n ! different adjacency matrices for a graph with n vertices, since there are n ! different ordering of n vertices. However, any two such adjacency matrices are closely related in that one can be obtained from the other by simply interchanging rows and columns. There are a number of observations that one can make about the adjacency matrix A of a graph G are :

Observations :
(i) A is symmetric i.e. aij = aji for all i and j
(ii) The entries along the principal diagonal of A all zeros if and only if the graph has no self loops. A self loop at the vertex corresponding to aij = 1.
(iii) If the graph is simple (no self loop, no parallel edges), the degree of vertex equals the number of 1’s in the corresponding row or column of A.
(iv) The (i, j) entry of Am is the number of paths of length (no. of occurence of edges) m from vertex vi vertex vj.
(v) If G be a graph with n vertices v1, v2, ...... vn and let A denote the adjacency matrix of G with respect to this listing of the vertices. Let B be the matrix.
^{B = A A2 A3 ...... An – 1}

Then G is a connected graph if B has no zero entries of the main diagonal.
This result can be also used to check the connectedness of a graph by using its adjacency matrix. Adjacency can also be used to represent undirected graphs with loops and multiple edges. A loop at the vertex v1 is represented by a 1 at the (i, j)th position of the adjacency matrix. When multiple edges are present, the adjacency matrix is no longer a zero-one matrix, since the (i, j)th entry equals the number of edges these are associated to {vi – vj}.
All undirected graphs, including multigraphs and pseudographs, have symmetric adjacency matrices.

(b) Representation of directed graph
The adjacency matrix of a diagonal D, with n vertices is the matrix A = {aij}n × n in which aij = 1 if arc {vi – vj} is in D = 0 otherwise. One can make a number of observations about the adjacency matrix of a diagonal. Observations

(i) A is not necessary symmetric, since there may not be an edges from vi to vj when there is an edge from vi to vj.
(ii) The sum of any column of j of A is equal to the number of arcs directed towards vj.

(iii) The sum of entries in row i is equal to the number of arcs directed away from vertex vi (out degree of vertex vi)
(iv) The (i, j) entry of Am is equal to the number of path of length m from vertex vi to vertex vj entries of AT. A shows the in degree of the vertices.

The adjacency matrices can also be used to represent directed multigraphs. Again such matrices are not zero-one matrices when there are multiple edges in the same direction connecting two vertices. In the adjacency matrix for a directed multigraph aij equals the number of edges that are associated to (vi, vj).

Incidence matrix

(a) Representation of undirected graph

Consider a undirected graph G = (V, E) which has n vertices and m edges all labelled. The incidence matrix B = {bij}, is then n × m matrix,
where bij = 1 when edge ej is incident with vi = 0 otherwise, We can make a number of observations about the incidence matrix B of G. Observations :

(i) Each column of B comprises exactly two unit entries.
(ii) A row with all O entries corresponds to an isolated vertex.
(iii) A row with a single unit entry corresponds to a pendent vertex.
(iv) The number of unit entries in row i of B is equal to the degree of the corresponding vertex vi.
(v) The permutation of any two rows (any two columns) of B corresponds to a labelling of the vertices (edges) of G.
(vi) Two graphs are isomorphic if and only if their corresponding incidence matrices differ only by a permutation of rows and columns.
(vii) If G is connected with n vertices then the rank of B is n – 1.

Incidence matrices can also be used to represent multiple edges and loops. Multiple edges are represented in the incidence matrix using columns with identical entries. Since these edges are incident with the same pair of vertices. Loops are represented using a column with exactly one entry equal to 1, corresponding to the vertex that is incident with this loop.

(b) Representation of directed graph
The incidence matrix B = {bij} of digraph D with n vertices and m edges is the n × m matrix in which

bij = 1 if arc j is directed away from a vertex vi

= – 1 if arc j directed towards vertex vi

= 0 otherwise.

Linked representation: In this representation, a list of vertices adjacent to each vertex is maintained. This representation is also called adjacency structure representation. In case of a directed graph, a case has to be taken, according to the direction of an edge, while placing a vertex in the adjacent structure representation of another vertex.