IB Mathematics Applications & Interpretation Question Type 4: Creating Directed Graphs Given Some Descriptions or Information Exercises

Warehouses must be visited in the following precedence constraints:

• $A$ before $B$ and $C$;
• $B$ before $D$;
• $C$ before $D$ and $E$;
• $D$ before $F$;
• $E$ before $F$.

Represent this as a directed acyclic graph and provide one possible topological ordering of the warehouses.

Consider a directed graph with vertices $A,B,C,D,E,F$ and the following travel times between vertices:

• $A\to B:4$
• $A\to C:2$
• $B\to C:1$
• $B\to D:5$
• $C\to D:8$
• $C\to E:10$
• $D\to F:6$
• $E\to F:2$

Use Dijkstra’s algorithm to find the shortest travel time and path from $A$ to $F$.

A directed graph consists of six vertices: $A,B,C,D,E,\text{ and }F$. The set of directed edges is given by:

$$\{A\to B,B\to C,C\to D,D\to E,E\to F,A\to C,C\to E\}$$

Determine whether there exists a Hamiltonian path in this graph that visits each vertex exactly once. Justify your answer.

Given six warehouses labeled $A,B,C,D,E,F$ and the one-way travel times (in hours) as follows: $A\to B:3$, $A\to C:5$, $B\to D:4$, $C\to D:2$, $D\to E:6$, $E\to F:1$.

Construct the adjacency matrix of the directed graph using $\infty$ for no direct connection.

Each directed arc between warehouses has a time window during which travel is allowed. The travel time for each arc is constant at $1$ unit. The allowed departure windows are as follows:

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

Construct the time-expanded network for integer times $t=0$ to $t=8$, indicating the nodes and all feasible time-step edges (including waiting edges).

A directed graph has vertices $V=\{A,B,C,D,E,F\}$ and the following weighted edges:

• $A\to B:3$
• $A\to C:2$
• $B\to D:4$
• $C\to D:6$
• $B\to E:5$
• $C\to E:3$
• $D\to F:1$
• $E\to F:2$

Find the minimum spanning arborescence rooted at $A$ using Chu–Liu/Edmond’s algorithm. State the set of edges included in the arborescence and calculate its total weight.

Draw on this

The one-way shipping costs (in dollars) between six warehouses are: $A\to B:10$, $A\to C:15$, $B\to C:4$, $B\to D:12$, $C\to E:10$, $D\to F:5$, $E\to F:10$. Represent this as an adjacency list for the directed graph.

Using the directed graph $G$, determine whether it is strongly connected. Justify your answer.

Consider a directed graph with vertices $V=\{A,B,C,D,E,F\}$ and the following edges: $A\to B$, $B\to C$, $C\to D$, $D\to E$, $E\to F$, $A\to C$, and $C\to E$.

Determine whether there is an Eulerian circuit in this graph. Justify your answer.

Six warehouses are located at coordinates $A(0,0)$, $B(2,3)$, $C(5,1)$, $D(6,4)$, $E(3,5)$, and $F(1,4)$. A complete graph is constructed where the weight of each edge is the Euclidean distance between the warehouses, rounded to the nearest integer.

Starting from warehouse $A$, use the nearest-neighbour algorithm to determine a Hamiltonian cycle that visits each warehouse exactly once and returns to $A$.

State the sequence of warehouses in the cycle and calculate the total distance.

The following one-way shipping costs (in $) form a directed graph: $A\to B:20$, $B\to C:30$, $C\to A:25$, $C\to D:15$, $D\to E:10$, $E\to F:5$, $F\to D:8$.

List the set of directed edges with their weights.