Adjacency matrices Problem set A

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

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

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

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

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

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

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

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

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

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