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

Question 1

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

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

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

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

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

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

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

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

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

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

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

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