Adjacency matrices Problem set B Worked solutions

Graph H is shown. Write down its adjacency matrix, with rows and columns in the order P, Q, R, S.

• Rows and columns in the order P, Q, R, S
• Entries: PQ, PR (2 edges), QS, RS, QR and a loop at P; an edge between two different vertices gives 1 in each of two places, a loop gives 2 on the diagonal
• \(\begin{pmatrix}2 & 1 & 2 & 0 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}\)

A graph has adjacency matrix \(\begin{pmatrix}2 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\), with rows and columns in the order P, Q, R, S.

1. (a) Draw the graph.

   • Read the entries above the diagonal for the edges between different vertices
   • A 2 on the diagonal is one loop
   • Edges: a loop at P, PQ, PS, QR (2 edges) and RS

2. (b) How many edges does it have?

   • Sum of the entries = 12
   • 12 ÷ 2 = 6 edges

The adjacency matrix of a graph is \(\begin{pmatrix}0 & 2 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 2\end{pmatrix}\), with rows and columns in the order P, Q, R, S, T.

1. (a) List the vertices adjacent to R.

   • Row R: [0, 1, 0, 1, 0]
   • The non-zero entries are in columns Q and S

2. (b) Find the degree of T.

   • 1 + 0 + 0 + 1 + 2 = 4

A directed graph has adjacency matrix \(\begin{pmatrix}0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\). Rows are the vertex an edge is from, columns the vertex it goes to, in the order P, Q, R, S.

1. (a) Find the out-degree of Q.

   • Row Q: [0, 0, 0, 1]
   • Out-degree = 1

2. (b) Find the in-degree of Q.

   • Column Q: [1, 0, 1, 0]
   • In-degree = 2

3. (c) Find the number of edges.

   • Sum of all the entries = 7

A directed graph has adjacency matrix \(\begin{pmatrix}0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0\end{pmatrix}\). Rows are the vertex an edge leaves, in the order P, Q, R, S.

1. (a) Draw the directed graph.

   • A 1 in row i, column j is an edge from i to j
   • Edges: P to R, P to S, Q to P, Q to R, S to Q and S to R

2. (b) Which vertex has the greatest in-degree?

   • In-degrees (column sums): P 1, Q 1, R 3, S 1
   • R is greatest

The diagram shows the one-way ferry routes between five islands.

1. (a) Write down the adjacency matrix, with rows for the starting island and columns for the destination, in alphabetical order.

   • Row = from, column = to. Put 1 for each arrow
   • \(\begin{pmatrix}0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0\end{pmatrix}\)

2. (b) Which island has the greatest out-degree?

   • Row sums: P 0, Q 1, R 1, S 3, T 2
   • Greatest: S

3. (c) Which island has the greatest in-degree?

   • Column sums: P 2, Q 3, R 1, S 0, T 1
   • Greatest: Q

The matrix shows the number of direct cables between four offices. \(\begin{pmatrix}0 & 2 & 1 & 0 \\ 2 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0\end{pmatrix}\) Rows and columns are in the order W, X, Y, Z.

1. (a) Which places are joined directly to X?

   • Row X: [2, 0, 1, 1]
   • Non-zero entries: W, Y and Z

2. (b) How many edges are there in all?

   • Sum of all entries = 10
   • 10 ÷ 2 = 5

3. (c) Which place has the greatest degree, and what is it?

   • Row sums: W 3, X 4, Y 2, Z 1
   • X is greatest

Four teams pass parcels to each other in a relay game. The matrix shows how many parcels each team passed to each. \(\begin{pmatrix}0 & 1 & 0 & 2 \\ 3 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 2 & 0\end{pmatrix}\) Rows are the sender and columns the receiver, in the order W, X, Y, Z.

1. (a) Which team sends the most parcels?

   • Row sums (out-degrees): W 3, X 6, Y 1, Z 3
   • Most: X

2. (b) Which team receives the most parcels?

   • Column sums (in-degrees): W 4, X 1, Y 3, Z 5
   • Most: Z

3. (c) How many parcels were sent in all?

   • Sum of all the entries = 13

An undirected graph has adjacency matrix \(M=\begin{pmatrix}0 & 2 & x \\ 2 & 2 & 1 \\ x & 1 & 0\end{pmatrix}\). Vertex 3 has degree 5.

1. (a) Find the value of x.

   • Degree of vertex 3 = row sum: x + 1 + 0 = 5
   • 1 + x = 5
   • x = 4

2. (b) Find the number of edges.

   • Sum of all the entries = 16
   • Edges = 16 ÷ 2 = 8

A directed graph has adjacency matrix \(M=\begin{pmatrix}0 & 1 & x & 0 \\ 2 & 0 & 1 & 1 \\ y & 0 & 0 & 1 \\ 0 & 1 & 0 & 0\end{pmatrix}\), with rows and columns in the order P, Q, R, S. Rows are the vertex an edge leaves. The out-degree of P is 4 and its in-degree is 5.

1. (a) Find the value of x.

   • Out-degree = row sum: 0 + 1 + x + 0 = 4
   • 1 + x = 4
   • x = 3

2. (b) Find the value of y.

   • In-degree = column sum: 0 + 2 + y + 0 = 5
   • 2 + y = 5
   • y = 3