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.

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.