84

Representation of Graphs

There are two principal ways to represent a graph G with the matrix, i.e., adjacency matrix and incidence matrix representation.

(a)Representation of the Undirected Graph:

1. Adjacency Matrix Representation: If an Undirected Graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [a_ij] and defined by

If there exists an edge between vertex v_i and v_j, where i is a row and j is a column then the value of a_ij=1.

If there is no edge between vertex v_i and v_j, then value of a_ij=0.

Example: Find the adjacency matrix M_A of graph G shown in Fig:

Solution: Since graph G consist of four vertices. Therefore, the adjacency matrix wills a 4 x 4 matrix. The adjacency matrix is as follows in fig:

2. Incidence Matrix Representation: If an Undirected Graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix C = [c_ij] and defined by

There is a row for every vertex and a column for every edge in the incident matrix.

The number of ones in an incidence matrix of the undirected graph (without loops) is equal to the sum of the degrees of all the vertices in a graph.

Example: Consider the undirected graph G as shown in fig. Find its incidence matrix M_I.

Solution: The undirected graph consists of four vertices and five edges. Therefore, the incidence matrix is an 4 x 5 matrix, which is shown in Fig:

(b)Representation of Directed Graph:

1. Adjacency Matrix Representation: If a directed graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [a_ij] and defined by

If there exists an edge between vertex V_i and V_j, with V_i as initial vertex and V_j as a final vertex, then the value of a_ij=1.

If there is no edge between vertex V_i and V_j, then the value of a_ij=0.

The number of ones in the adjacency matrix of a directed graph is equal to the number of edges.

Example: Consider the directed graph shown in fig. Determine its adjacency matrix M_A.

Solution: Since the directed graph G consists of five vertices. Therefore, the adjacency matrix will be a 5 x 5 matrix. The adjacency matrix of the directed graphs is as follows:

2. Incidence Matrix Representation: If a directed graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix C = [c_ij] and defined by

The number of ones in an incidence matrix is equal to the number of edges in the graph.

Example: Consider the directed graph G as shown in fig. Find its incidence matrix M_I.

Solution: The directed graph consists of four vertices and five edges. Therefore, the incidence matrix is a 4 x 5 matrix which is show in fig:

(c)Representation of Multigraph:

Represented only by adjacency matrix representation.

(i)Adjacency matrix representation of multigraph: If a multigraph G consists of vertices, then the adjacency matrix of graph is an n x n matrix A = [a_ij] and is defined by

If there exist one or more than one edges between vertex v_i and v_j then a_ij=N, where is the number of edges between v_i and v_j.

If there is no edge between v_i and v_j.

Example: Consider the multigraph shown in Fig, Determine its adjacency matrix.

Solution: Since the multigraph consist of five vertices. Therefore the adjacency matrix will be an 5 x 5 matrix. The adjacency matrix of the multigraph is as follows:

---