RevisionDojo

Question 1

Skill question

Find the degree sequence of the graph whose adjacency matrix on vertices $1$ – $6$ is:

A=\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}

Question 2

Skill question

Given the adjacency matrix of a simple undirected graph on vertices $1,2,3,4$ as follows:

A=\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}

List all edges of the graph.

Question 3

Skill question

The adjacency list of a graph $G$ is:

A: B, D B: A, C, D C: B, D D: A, B, C

Determine whether $G$ is connected.

Question 4

Skill question

For the graph with adjacency matrix

A=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}

determine the number of connected components.

Question 5

Skill question

Construct the adjacency matrix of the directed graph with vertex set $\{1,2,3,4\}$ and directed edges:

2\to3, 3\to1, 3\to4, 4\to2.$$

Question 6

Skill question

Determine whether the graph with adjacency matrix on vertices $1$ through $5$ below is a tree:

A=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}

Question 7

Skill question

Determine if the graph represented by

A=\begin{pmatrix} 0 & 2 & 2 & 2 \\ 2 & 0 & 2 & 2 \\ 2 & 2 & 0 & 2 \\ 2 & 2 & 2 & 0 \end{pmatrix}

is regular, and if so state its degree.

Question 8

Skill question

Test if the graph given by the adjacency matrix below is bipartite:

A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}

Question 9

Skill question

Check whether the graph given by the adjacency matrix below has an Eulerian circuit:

A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix}

Question 10

Skill question

Using the adjacency matrix below, find a shortest path from vertex $1$ to vertex $5$ in the unweighted graph.

A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}

Question 11

Skill question

Decide whether the graph with adjacency matrix below has a Hamiltonian path.

A=\begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{pmatrix}

Question 12

Skill question

Given the weighted adjacency matrix of a connected undirected graph on vertices $1$ – $5$ :

W=\begin{pmatrix} 0 & 2 & 0 & 6 & 0 \\ 2 & 0 & 3 & 8 & 5 \\ 0 & 3 & 0 & 0 & 7 \\ 6 & 8 & 0 & 0 & 9 \\ 0 & 5 & 7 & 9 & 0 \end{pmatrix}

find a minimum spanning tree using Kruskal’s algorithm.

Question Type 3: Using adjacency tables to reconstruct graphs or check graph properties Exercises