• Home
  • /
  • Blog
  • /
  • 2 Essential Concepts of Graph Explained for Kids Advantage

2 Essential Concepts of Graph Explained for Kids Advantage

2 Essential Concepts of Graph Explained for Kids Advantage

This post is also available in: हिन्दी (Hindi) العربية (Arabic)

A graph with n nodes can be represented in the form of a square matrix of order n. In this article, we bring 2 Essential Concepts of Graph Explained for Kids Advantage. These are the Adjacency Matrix and Path Matrix.

Adjacency Matrix and Path Matrix

A network usually consists of hundreds or thousands of nodes connected to one another by edges. These networks can be represented as graphs, a type of data structure. Have you ever wondered how a path between two nodes is established to facilitate uninterrupted communication? 

To understand this, one should know two basic concepts of graphs.

  • Adjacency Matrix
  • Path Matrix

Adjacency Matrix

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Elements of an adjacency matrix are either 0 or 1. If a pair of nodes have a common edge(i.e., nodes are connected), it is represented by 1. If a pair of nodes do not have a common edge(i.e., nodes are not connected), it is represented by 0.

Let’s now understand how undirected and directed graphs are represented by an adjacency matrix.

Adjacency Matrix – Undirected Graph

Adjacency Matrix and Path Matrix
Undirected Graph

In this graph node A is adjacent to nodes B and C. Similarly, node B is adjacent to nodes A and C; node C is adjacent to nodes A, B, and D; node D is adjacent to node C.

The adjacency matrix of the above graph is

ABCD
A01100110
B1010=1010
C11011101
D00100010
Adjacency Matrix

In the above matrix, since there is a path from A to C as well as from C to A, therefore, entry for A to C and C to A is 1. The same is true for other nodes.

In the case when a node is connected to itself by a loop. (Node C has a loop).

Adjacency Matrix and Path Matrix
Undirected Graph with Loop
ABCD
A01100110
B1010=1010
C11111111
D00100010
Adjacency Matrix

Adjacency Matrix – Directed Graph

Adjacency Matrix and Path Matrix
Direct Graph with Loop

Consider a directed graph as shown above. There is a path from node A to node B, but there doesn’t exist any direct path from node B to node A. Similarly there is a path from node C to node A but no such path between node A to node C.

Now consider a pair of nodes B and C. There is a direct path from node B to node C as well as from node C to node B. The adjacency matrix of the above graph is represented as

ABCD
A01000100
B0010=0010
C11111111
D00000000

Path Matrix

Consider the following graph

Adjacency Matrix and Path Matrix
Directed Graph

The adjacency matrix of the above graph is 

ABCDE
A0101001010
B00100=00100
C0000100001
D0100001000
E0001000010

If we consider the pair of nodes B and E. From the above adjacency matrix, we find that there is no direct path between B and E. But there exists a  path from B and E through C. Such a path is known as a path of length 2. Similarly, a path of length 3 will have 2 intermediate nodes. In general, a path of length n will have (n – 1) intermediate nodes. 

To obtain a path matrix of length 2, the adjacency matrix is multiplied by itself.

010100101001100
001000010000001
0000100001=00010
010000100000100
000100001001000

From the above matrix, we find that there exists a path of length 2 between A to B, E to B, A to C, D to C, C to D, and B to E.

Again multiplying the path matrix of length 2 with the adjacency matrix gives a path matrix of length 3.

011000101000101
000010010000010
0001000001=01000
001000100000001
010000001000100

From the above matrix, we find that there exists a path of length 3 between C to B, A to C, E to C, B to D, A to E, and D to E.

In general, to generate the matrix of the path of length n, take the matrix of the path of length (n – 1), and multiply it with the matrix of a path of length 1.

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>