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

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.

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

Is the directed graph from question 1 strongly connected? Justify your answer.

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.

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

In the graph from question 6, determine if there is a path from $W_3$ to $W_6$. If yes, provide one such path and its total cost.

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

For the warehouse graph in question 6, find the out-degree of each vertex (count only existing routes).

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

Does the directed graph from question 6 contain an Eulerian circuit? Justify your answer by comparing in-degrees and out-degrees.

Identify the strongly connected components of the directed graph in question 6.

Using the adjacency matrix from question 11, determine the shortest path from $A$ to $E$ and its total cost.