Question Type 4: Creating directed graphs given some descriptions or information Exercises

Given six warehouses labeled A, B, C, D, E, F and the one-way travel times (in hours) as follows: A→B: 3, A→C: 5, B→D: 4, C→D: 2, D→E: 6, E→F: 1. Construct the adjacency matrix of the directed graph using $\infty$ for no direct connection.

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

The following one-way shipping costs (in $) form a directed graph: A→B: 20, B→C: 30, C→A: 25, C→D: 15, D→E: 10, E→F: 5, F→D: 8. List the set of directed edges with their weights.

Using the directed graph from the previous question, determine whether it is strongly connected. Justify your answer.

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 the directed graph with vertices A,B,C,D,E,F and edges with travel times: A→B: 4, A→C: 2, B→C: 1, B→D: 5, C→D: 8, C→E: 10, D→F: 6, E→F: 2. Use Dijkstra’s algorithm to find the shortest travel time and path from A to F.

Given the directed graph with edges: A→B, B→C, C→D, D→E, E→F and an extra edge A→C and C→E (all edges weight irrelevant), determine whether there exists a Hamiltonian path visiting each warehouse exactly once.

Using the same directed graph as above (edges A→B, B→C, C→D, D→E, E→F, A→C, C→E), determine whether there is an Eulerian circuit. Justify your answer.

Construct the directed network representing capacities for six warehouses with edges and capacities: A→B: 10, A→C: 5, B→D: 6, C→D: 4, B→E: 4, D→F: 8, E→F: 6. Compute the maximum flow from A to F using the Ford–Fulkerson method.

For the directed graph with vertices A,B,C,D,E,F and weighted edges A→B: 3, A→C: 2, B→D: 4, C→D: 6, B→E: 5, C→E: 3, D→F: 1, E→F: 2, find the minimum spanning arborescence rooted at A using Chu–Liu/Edmond’s algorithm.

Six warehouses are located at coordinates: A(0,0), B(2,3), C(5,1), D(6,4), E(3,5), F(1,4). Construct a directed graph where each one-way distance is the Euclidean distance rounded to the nearest integer. Then, starting from A, apply the nearest-neighbour heuristic to find a route visiting all warehouses exactly once. State the route and total distance.

Each directed arc between warehouses has a time window during which travel is allowed: A→B: 0–4, B→C: 2–6, C→D: 3–7, D→E: 1–5, E→F: 4–8. Construct the time-expanded network for integer times t=0 to t=8, indicating nodes and feasible time-step edges.