RevisionDojo

Question 1

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}

[3 marks]

[3]

Question 2

The question requires determining if a graph is regular and finding its degree using a given adjacency matrix for a multigraph.

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.

[3]

Question 3

Decide whether the graph with adjacency matrix $A$ 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}

[4]

Question 4

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

[3]

Question 5

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.

[2]

Question 6

Testing for bipartiteness in a graph using an adjacency matrix representation and vertex coloring.

Determine whether the graph represented by the adjacency matrix $\mathbf{A}$ below is bipartite. Justify your answer.

\mathbf{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}

[4]

Question 7

Graph theory: properties of trees and adjacency matrices.

Determine whether the graph with the following adjacency matrix $A$ on vertices $1$ through $5$ 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}

[3]

Question 8

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.

[3]

Question 9

The question requires finding the Minimum Spanning Tree (MST) from a weighted adjacency matrix using Kruskal's algorithm, involving edge sorting and cycle detection.

Given the weighted adjacency matrix $W$ of a connected undirected graph with vertices $\{1, 2, 3, 4, 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. Show your working by listing the edges in the order they are selected and state the total weight of the tree.

[5]

Question 10

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.

[3]

Question 11

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}

[4]

Question 12

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}

[4]

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