1. Home
  2. Docs
  3. Discrete Structure
  4. Graphs
  5. Representation of Graph

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 MatrixIncidence MatrixAdjacency List

‣ Adjacency Matrix:

Let G=(V,E) be a graph with n vertices: v1, v2, v3, …… Vn. The adjacency matrix of G with respect to given ordered list of vertices is a nxn matrix denoted by A(G)=(aij)nxn.
such that,

image 112

Undirected graph representation

image 109

Directed graph represenation

image 110

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 MA of undirected graph G shown in Fig:

image 114

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:

image 115

‣ Incidence Matrix:

Let G be a graph with vertices v1, v2,…. vm and edges e1, e2,… en. The incidence matrix I(G) of graph G is a mxn matrix with I(G) = (mij)mxn.
such that,

image 113
image 111

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

image 116

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:

image 117

‣ 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:

WhatsApp Image 2023 09 27 at 18.42.06

Directed Graph fig:

image 118

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *