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

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: Vertex 1234 Neighbors with weights (2, 4), (3, 1) (1, 4), (3, 2), (4, 5) (1, 1), (2, 2), (4, 3) (2, 5), (3, 3) Reconstruct the graph and label each edge with its weight.

[4]

Question 3

The adjacency table of an undirected graph is: V 12345 Neighbors 2, 3 1, 4 1, 4 2, 3, 5 4 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: V 123456 Adjacency List 2 1, 3 2, 4 365

[3]

Question 5

Given the undirected unweighted graph with vertex set V = {A, B, C, D, E} and edge set E = {A B, A C, B D, C E, D E}, 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. V A B C D Neighbors B, C A, D A, D B, C

[5]

Question 7

Given the adjacency list for an undirected graph: V u v w x Adjacency List v, w u, w, x u, v, x v, w Decide if the graph has an Eulerian circuit. Justify your answer.

[3]

Question 8

Consider a directed graph defined by the following adjacency table: V P Q R S Outgoing Arcs Q, R R P Q, R

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: Vertex P Q R S T Adjacency List Q, R P, R, S P, Q, T Q R

[4]

Question 11

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

[2]

Question 12

From the adjacency table below for an undirected graph, compute the degree of each vertex: V a b c d e Adjacency List b, c, d a, d a, d a, b, c, e d

[3]

IB Mathematics Applications & Interpretation Question Type 2: Creating Adjacency Tables for Weighted and Unweighted Graphs Exercises