Adjacency matrices Problem set B

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

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.
2. (b) How many edges does it have?

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.
2. (b) Find the degree of T.

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.
2. (b) Find the in-degree of Q.
3. (c) Find the number of edges.

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.
2. (b) Which vertex has the greatest in-degree?

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.
2. (b) Which island has the greatest out-degree?
3. (c) Which island has the greatest in-degree?

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?
2. (b) How many edges are there in all?
3. (c) Which place has the greatest degree, and what is it?

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?
2. (b) Which team receives the most parcels?
3. (c) How many parcels were sent in all?

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.
2. (b) Find the number of edges.

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.
2. (b) Find the value of y.