Exercises for Question Type 3: Determining properties of a given directed graph

Question 1

Skill question

The following question requires the construction of a directed graph and the formulation of its weighted adjacency matrix based on given network data.

Six warehouses $W_{1}$ to $W_{6}$ are connected by directed routes with costs (in hundreds of dollars):

$W_{1} \to W_{2} : 5$ , $W_{1} \to W_{3} : 8$ , $W_{2} \to W_{4} : 4$ , $W_{3} \to W_{5} : 6$ , $W_{5} \to W_{6} : 7$ , $W_{4} \to W_{6} : 3$ , $W_{6} \to W_{1} : 9$ .

Construct the directed graph and write its weighted adjacency matrix (use 0 for no route).

[5]

Question 2

Skill question

The following directed graph consists of six vertices, $W_{1}, W_{2}, W_{3}, W_{4}, W_{5}$ , and $W_{6}$ .

Identify the strongly connected components of the directed graph.

[5]

Question 3

Skill question

Six warehouses $A, B, C, D, E, F$ must be visited by a delivery truck starting at $A$ . The directed routes and costs are:

$A \to B : 2$ , $A \to C : 4$ , $B \to D : 7$ , $C \to D : 1$ , $D \to E : 3$ , $E \to F : 5$ , $F \to A : 6$ , $B \to E : 2$ , $C \to F : 8$ .

Represent this scenario as a directed graph with weighted edges and write its adjacency matrix (use $\infty$ for no direct route).

[5]

Question 4

Skill question

The following adjacency matrix represents the weights of edges between five vertices $A$ , $B$ , $C$ , $D$ , and $E$ in a weighted graph:

$A B C D E A 024 \infty \infty B 20 \infty 72 C 4 \infty 01 \infty D \infty 710 \infty E \infty 2 \infty \infty 0$

Using Dijkstra’s algorithm, determine the shortest path from $A$ to $E$ and state its total cost.

[6]

Question 5

Skill question

Directed graphs and reachability.

Given the directed graph $G$ with edges $E = {A \to B, B \to C, A \to D, D \to C, C \to E}$ , list all vertices reachable from $A$ .

[2]

Question 6

Skill question

A directed graph $G$ consists of four vertices $A$ , $B$ , $C$ , and $D$ . The graph contains the path $A \to C \to D$ , but vertex $D$ has no outgoing edges.

Determine whether the graph $G$ is strongly connected. Justify your answer.

[3]

Question 7

Skill question

The following directed graph shows the transport costs (in hundreds of dollars) between six warehouses, denoted as $W_{1}, W_{2}, W_{3}, W_{4}, W_{5},$ and $W_{6}$ .

Determine if there is a path from $W_{3}$ to $W_{6}$ . If a path exists, provide one such path and calculate its total cost.

[3]

Question 8

Skill question

The following directed graph shows the delivery routes between six warehouses, $W_{1}, W_{2}, W_{3}, W_{4}, W_{5},$ and $W_{6}$ .

Determine the out-degree of each vertex.

[2]

Question 9

Skill question

In a directed graph $G$ , vertex $W_{1}$ has two outgoing edges and one incoming edge.

Determine whether $G$ contains an Eulerian circuit. Justify your answer by comparing in-degrees and out-degrees.

[3]

Question 10

Skill question

Convert the following adjacency list into an adjacency matrix for the directed graph with vertices $V = {X, Y, Z}$ .

Adjacency list:

$X$ : $Y, Z$
$Y$ : $Z$
$Z$ : $X$

[2]

Question 11

Skill question

Given the directed graph $G$ with vertices $V = {A, B, C, D}$ and edges $E = {A \to B, A \to C, B \to C, C \to D}$ , find the in-degree and out-degree of each vertex.

[5]

Question 12

Skill question

Level: HL | Paper: 1

Consider the adjacency matrix of a directed graph with vertices $V = {1, 2, 3, 4}$ given by

$A = 0010100001011000 .$ Compute the in-degree and out-degree of vertex 3.

[2]

IB Mathematics Applications & Interpretation Question Type 3: Determining Properties of a Given Directed Graph Exercises