Adjacency matrices Problem set A One question at a time

Graph G is shown. Write down its adjacency matrix, with rows and columns in the order A, B, C, D.

• Rows and columns in the order A, B, C, D
• Entries: AB, BC (2 edges), CD, AC and a loop at D; an edge between two different vertices gives 1 in each of two places, a loop gives 2 on the diagonal
• \(\begin{pmatrix}0 & 1 & 1 & 0 \\ 1 & 0 & 2 & 0 \\ 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2\end{pmatrix}\)

A graph has adjacency matrix \(\begin{pmatrix}0 & 2 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\), with rows and columns in the order A, B, C, D.

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: AB (2 edges), AD, BC, a loop at C and CD

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 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 2 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 2\end{pmatrix}\), with rows and columns in the order A, B, C, D, E.

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

   • Row C: [1, 0, 0, 1, 1]
   • The non-zero entries are in columns A, D and E

2. (b) Find the degree of D.

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

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

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

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

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

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

3. (c) Find the number of edges.

   • Sum of all the entries = 6

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

1. (a) Draw the directed graph.

   • A 1 in row i, column j is an edge from i to j
   • Edges: A to B, A to C, B to C, C to A and D to C

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

   • In-degrees (column sums): A 1, B 1, C 3, D 0
   • C is greatest

The diagram shows the one-way flights offered by an airline between five cities.

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

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

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

   • Row sums: A 1, B 1, C 2, D 0, E 3
   • Greatest: E

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

   • Column sums: A 3, B 1, C 1, D 2, E 0
   • Greatest: A

The matrix shows the number of direct roads between four villages. \(\begin{pmatrix}0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 0\end{pmatrix}\) Rows and columns are in the order P, Q, R, S.

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

   • Row Q: [1, 0, 2, 1]
   • Non-zero entries: P, R and S

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: P 2, Q 4, R 2, S 2
   • Q is greatest

Four friends send each other messages in a group exercise. The matrix shows how many messages each sent to each. \(\begin{pmatrix}0 & 3 & 1 & 0 \\ 0 & 0 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0\end{pmatrix}\) Rows are the sender and columns the receiver, in the order A, B, C, D.

1. (a) Which friend sends the most messages?

   • Row sums (out-degrees): A 4, B 3, C 1, D 3
   • Most: A

2. (b) Which friend receives the most messages?

   • Column sums (in-degrees): A 1, B 5, C 4, D 1
   • Most: B

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

   • Sum of all the entries = 11

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

1. (a) Find the value of x.

   • Degree of vertex 1 = row sum: 2 + 1 + x = 6
   • 3 + x = 6
   • x = 3

2. (b) Find the number of edges.

   • Sum of all the entries = 14
   • Edges = 14 ÷ 2 = 7

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

1. (a) Find the value of x.

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

2. (b) Find the value of y.

   • In-degree = column sum: 0 + 1 + y + 1 = 4
   • 2 + y = 4
   • y = 2