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

Start Practicing

Worksheet: Adjacency Matrix

Q1:

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

Q2:

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 

Q3:

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 