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

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).

Identify the strongly connected components of the directed graph.

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).

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

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$.

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

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.

Determine the out-degree of each vertex.

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.

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$

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.

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

Compute the in-degree and out-degree of vertex 3.