RevisionDojo

Question 1

An undirected weighted graph has vertices $1, 2, 3, 4$ and the following weighted edges:

$\{1, 2\}$ with weight $5$
$\{1, 3\}$ with weight $2$
$\{2, 4\}$ with weight $7$
$\{3, 4\}$ with weight $4$

Create the adjacency table for this graph.

[3]

Question 2

Reconstruction of an undirected weighted graph from its adjacency table.

The weighted adjacency table of an undirected graph is:

\begin{array}{|c|l|} \hline \text{Vertex} & \text{Neighbors with weights} \\ \hline 1 & (2,4), (3,1) \\ \hline 2 & (1,4), (3,2), (4,5) \\ \hline 3 & (1,1), (2,2), (4,3) \\ \hline 4 & (2,5), (3,3) \\ \hline \end{array}

Reconstruct the graph and label each edge with its weight.

[4]

Question 3

The adjacency table of an undirected graph is:

\begin{array}{c|l} V & \text{Neighbors} \\ \hline 1 & 2,3 \\ 2 & 1,4 \\ 3 & 1,4 \\ 4 & 2,3,5 \\ 5 & 4 \end{array}

Determine the number of connected components in this graph.

[2]

Question 4

Using the adjacency list below for an undirected graph, determine if the graph is connected:

\begin{array}{c|l} V & \text{Adjacency List}\\\hline 1 & 2 \\ 2 & 1, 3 \\ 3 & 2, 4 \\ 4 & 3 \\ 5 & 6 \\ 6 & 5 \end{array}

[3]

Question 5

Given the undirected unweighted graph with vertex set $V = \{A, B, C, D, E\}$ and edge set $E = \{AB, AC, BD, CE, DE\}$ , construct its adjacency table.

[3]

Question 6

This question assesses the ability to determine if a graph is bipartite using a 2-colouring or partitioning algorithm.

The adjacency table below defines an undirected graph. Determine whether the graph is bipartite.

\begin{array}{c|l} V & \text{Neighbors} \\ \hline A & B, C \\ B & A, D \\ C & A, D \\ D & B, C \end{array}

[5]

Question 7

Given the adjacency list for an undirected graph:

\begin{array}{c|l} V & \text{Adjacency List}\\\hline u & v, w \\ v & u, w, x \\ w & u, v, x \\ x & v, w \end{array}

Decide if the graph has an Eulerian circuit. Justify your answer.

[3]

Question 8

Consider a directed graph defined by the following adjacency table:

\begin{array}{c|l} V & \text{Outgoing Arcs} \\ \hline P & Q, R \\ Q & R \\ R & P \\ S & Q, R \end{array}

Determine the in-degree and out-degree of each vertex.

[4]

Question 9

This question assesses the ability to represent a directed weighted graph using an adjacency table (list).

Construct the adjacency table for the directed weighted graph with vertices $A$ , $B$ , $C$ and arc weights: $A \to B (3)$ , $A \to C (6)$ , $B \to C (1)$ , and $C \to A (4)$ .

[3]

Question 10

Given the adjacency table below for an undirected graph, list all edges and sketch the graph:

\begin{array}{|c|l|} \hline \text{Vertex} & \text{Adjacency List} \\ \hline P & Q, R \\ \hline Q & P, R, S \\ \hline R & P, Q, T \\ \hline S & Q \\ \hline T & R \\ \hline \end{array}

[4]

Question 11

Convert the undirected adjacency list below into its adjacency matrix, ordering vertices as $A, B, C, D$ :

\begin{array}{c|l} V & \text{Neighbors}\\\hline A & B, D \\ B & A, C \\ C & B, D \\ D & A, C \end{array}

[2]

Question 12

From the adjacency table below for an undirected graph, compute the degree of each vertex:

\begin{array}{c|l} V & \text{Adjacency List}\\\hline a & b, c, d \\ b & a, d \\ c & a, d \\ d & a, b, c, e \\ e & d \end{array}

[3]

Question Type 2: Creating adjacency tables for weighted and unweighted graphs Exercises