GATE CS 2022 (Forenoon) — Question 58

Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)NAT2 marksHard

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 \leq j \leq i \leq 5 \\ 0, & \text{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 the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Graph Theory (Connectivity, Paths, Cycles, Trees)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group