GATE 2022 CS – Question 58
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, & 1\le j\le i\le5\\0, & otherwise\end{cases}$
$A[i][j]=1$ indicates a directed edge from node $i$ to node $j$. A directed spanning tree of $G$, rooted at $r\in 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 _____________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 24
Explanation
$A[i][j]=1$ for $j\le i$: there is an edge $i\to j$ whenever $j\le i$ (including self-loops). From vertex 5 we can reach every smaller vertex.
A directed spanning tree rooted at 5 needs every non-root vertex to have **exactly one incoming tree edge**, coming from a vertex that can reach it.
An edge $u\to v$ exists iff $v\le u$, so vertex $v$ can receive an edge only from a **larger** vertex:
- vertex 4: from 5 only $\Rightarrow$ 1 choice
- vertex 3: from 4 or 5 $\Rightarrow$ 2 choices
- vertex 2: from 3, 4 or 5 $\Rightarrow$ 3 choices
- vertex 1: from 2, 3, 4 or 5 $\Rightarrow$ 4 choices
Any such choice creates no cycle (edges always go from larger to smaller), and every vertex is reachable from 5. Number of trees $=1\cdot2\cdot3\cdot4=\mathbf{24}$.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2021 CS (CS1) Q26
- GATE 2020 CS Q62
- GATE 2019 CS Q22
- GATE 2019 CS Q56
- GATE 2018 CS Q28
- GATE 2018 CS Q53
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →