RevisionDojo

Exercises for Question Type 5: Applying adjacency matrices with some real world context - IB | RevisionDojo

Question 1

Skill question

The undirected graph $G$ has adjacency matrix:

A=\begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 0\end{pmatrix}$$ What is the degree of vertex 2 in $G$?

Question 2

Skill question

Given the adjacency matrix of an undirected graph with 4 vertices:

A=\begin{pmatrix}0 & 1 & 0 & 1\\1 & 0 & 1 & 0\\0 & 1 & 0 & 1\\1 & 0 & 1 & 0\end{pmatrix},$$ how many edges does the graph contain?

Question 3

Skill question

In a social network, the adjacency matrix $A$ ( $A_{ij}=1$ if users $i,j$ are friends, 0 otherwise) is

A=\begin{pmatrix}0 & 1 & 1 & 0\\1 & 0 & 1 & 1\\1 & 1 & 0 & 0\\0 & 1 & 0 & 0\end{pmatrix}.$$ How many mutual friends do users 1 and 2 share?

Question 4

Skill question

A directed graph has adjacency matrix

A=\begin{pmatrix}0 & 1 & 1\\0 & 0 & 1\\1 & 0 & 0\end{pmatrix}$$ Compute the number of distinct paths of length 2 from vertex 1 to vertex 3.

Question 5

Skill question

Construct the adjacency matrix for a directed network of 4 nodes where edges are: $1\to2$ , $2\to3$ , $3\to4$ , $4\to1$ and $2\to4$ .

Question 6

Skill question

A transportation network of 3 cities has adjacency matrix

A=\begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 0\end{pmatrix},$$ where $A_{ij}=1$ if there is a direct bus route. How many different two-bus‐ride itineraries exist from city 1 to city 2 (allowing revisits)?

Question 7

Skill question

In a social network with adjacency matrix $A$ for 5 users, the number of paths of length 3 between user 1 and user 5 is given by entry $(A^3)_{1,5}=4$ . Explain the interpretation of this number in context.

Question 8

Skill question

A flight network of 4 airports is given by adjacency matrix

A=\begin{pmatrix}0 & 1 & 0 & 1\\1 & 0 & 1 & 1\\0 & 1 & 0 & 1\\1 & 1 & 1 & 0\end{pmatrix}$$ Calculate the number of distinct two-leg flight options from airport 1 to airport 3.

Question 9

Skill question

For the directed graph in the previous question, determine whether the graph is strongly connected.

Question 10

Skill question

A weighted adjacency matrix for 3 warehouses shows shipping times (in hours):

W=\begin{pmatrix}0 & 2 & 5\\2 & 0 & 3\\5 & 3 & 0\end{pmatrix}.$$ Ignoring weights, find how many distinct two-hop routes exist from warehouse 1 to warehouse 3.

Question 11

Skill question

Use the adjacency matrix of the directed graph below to compute the reachability matrix (transitive closure).
![DIAGRAM DESCRIPTION: Four nodes 1→2→3→4 with edges 1→2, 2→3, 3→4]
Label nodes in order 1 to 4.

Question 12

Skill question

A social network’s adjacency matrix $A$ is

A=\begin{pmatrix}0 & 1 & 1 & 0\\1 & 0 & 1 & 1\\1 & 1 & 0 & 1\\0 & 1 & 1 & 0\end{pmatrix}.$$ Determine if the network is bipartite.

Question 13

Skill question

Given an undirected graph with adjacency matrix $A$ , show that the trace of $A^3$ equals $6$ times the number of triangles in the graph.

Question 14

Skill question

Compute the eigenvector centrality of node 1 in the 2×2 adjacency matrix

A=\begin{pmatrix}0 & 1\\1 & 0\end{pmatrix}$$ by finding the normalized eigenvector corresponding to the largest eigenvalue.

Question Type 5: Applying adjacency matrices with some real world context Exercises