Let G(V, E) be a directed graph, where V = {1, 2,3, 4,5} is the set of…
2022
Let G(V, E) be a directed graph, where V = {1, 2,3, 4,5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.
\(A[i][j] = \begin{cases}1 & \text{if } 1 \leq j \leq i \leq 5 \\0 & \text{otherwise}\end{cases}\)
𝐴[𝑖][𝑗] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r ∈ V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is_____________.
Attempted by 77 students.
Show answer & explanation
Correct answer: 24
Key insight: every directed edge goes from a vertex with a larger index to one with a smaller or equal index (A[i][j]=1 iff j ≤ i). Self-loops do not help connect different vertices, so for forming a directed spanning tree rooted at 5, each non-root vertex must choose a parent with a strictly larger index.
Vertex 4 can only have parent 5 → 1 choice
Vertex 3 can have parent 4 or 5 → 2 choices
Vertex 2 can have parent 3, 4, or 5 → 3 choices
Vertex 1 can have parent 2, 3, 4, or 5 → 4 choices
Because every choice for each vertex is independent, and edges always go from higher to lower indices (so no cycles and every chain reaches 5), multiply the choices: 1 × 2 × 3 × 4 = 24. Thus the number of directed spanning trees rooted at vertex 5 is 24.
A video solution is available for this question — log in and enroll to watch it.