Representation of Graph

In graph theory, a graph representation is a technique to store graph into the memory of computer.

• There are mainly three ways to represent a graph −

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

‣ Adjacency Matrix:

Let G=(V,E) be a graph with n vertices: v₁, v₂, v₃, …… V_n. The adjacency matrix of G with respect to given ordered list of vertices is a nxn matrix denoted by A(G)=(a_ij)_nxn.
such that,

Undirected graph representation

Directed graph represenation

In the above examples, 1 represents an edge from row vertex to column vertex, and 0 represents no edge from row vertex to column vertex.

Q). Find the adjacency matrix M_A of undirected 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:

‣ Incidence Matrix:

Let G be a graph with vertices v₁, v₂,…. v_m and edges e₁, e₂,… e_n. The incidence matrix I(G) of graph G is a mxn matrix with I(G) = (m_ij)_mxn.
such that,

Q). Consider the undirected graph G as shown in fig. Find its incidence matrix MI.

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:

‣ Adjacency List:

An adjacency list provides a collection of the combinations of connected vertices in a graph.

This type of graph is suitable for the undirected graphs without multiple edges, and directed graphs.

UnDirected Graph fig:

Directed Graph fig: