Worksheet: Adjacency Matrix

In this worksheet, we will practice using a matrix to represent adjacency in a network as an application of matrices for the graph theory.

Q1:

Write down the adjacency matrix of the network shown.

  • A 2 0 0 0 0 1 0 1 1
  • B 0 0 0 0 1 1 2 1 0
  • C 0 0 0 1 0 1 0 1 1
  • D 0 0 0 2 0 1 0 1 1
  • E 1 0 0 0 0 1 0 1 1

Q2:

When a connection in a network does not have an arrow, it is said to be ‘undirected’. An undirected connection between nodes 𝑎 and 𝑏 is equivalent to a directed connection from 𝑎 to 𝑏 together with a directed connection from 𝑏 to 𝑎 . Determine the adjacency matrix of the network shown.

  • A 0 1 2 1 0 0 2 0 0
  • B 1 1 1 1 0 0 1 0 0
  • C 0 1 1 1 0 0 1 0 0
  • D 1 1 2 1 0 0 2 0 0
  • E 0 0 2 0 1 1 2 1 1

Q3:

Shown is a network whose adjacency matrix is

A succession of connections starting from one node and ending at another is called a path. The length of a path is the number of connections used. For example, “2e1” is a path of length 1 from node 2 to node 1, “ 2 𝑒 𝑏 3 ” is a path of length 2 from node 2 to node 3, and “ 2 𝑒 𝑒 𝑒 1 ” is a path of length 3 from node 2 to node 1.

List all the paths of length 2 from node 1 to node 1.

  • A 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 1
  • B 1 𝑎 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 𝑒 1
  • C 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 2 , 1 𝑑 𝑑 2 , 1 𝑒 𝑑 2 , 1 𝑒 𝑒 2
  • D 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 1
  • E 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 2 , 1 𝑑 𝑑 2 , 1 𝑒 𝑑 1 , 1 𝑒 𝑑 2 , 1 𝑒 𝑒 2

The number of paths of length 𝑛 from node 𝑖 to node 𝑗 is given by ( 𝐴 ) 𝑛 𝑖 , 𝑗 , the ( 𝑖 , 𝑗 ) th entry of the matrix 𝐴 𝑛 . How many paths of length 3 are there from node 1 to node 2?

  • A 18 paths
  • B 22 paths
  • C 26 paths
  • D 23 paths
  • E 16 paths

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.