GATE CSE 2022 | Question: 48

Question

Let $\textit{G(V,E)}$ be a directed graph, where $\textit{V} = \{ 1, 2, 3, 4, 5 \}$ is the set of vertices and $\textit{E}$ is the set of directed edges, as defined by the following adjacency matrix $\textit{A}.$
$$A [i][j] = \left\{\begin{matrix} 1, & 1 \leq j \leq i \leq 5 \\ 0, & \text{otherwise}\end{matrix}\right.$$ $A[i][j] = 1$ indicates a directed edge from node $i$ to node $j.$ A $\textit{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 __________________.

Comments

	1	2	3	4	5
1	1	0	0	0	0
2	1	1	0	0	0
3	1	1	1	0	0
4	1	1	1	1	0
5	1	1	1	1	1

Adjacency matrix of graph , if we draw a directed graph then we get know that here DAG concept is used bcoz there will always have a path from root vertex $5$​ to each vertex i.e. $1$ $$  $2$  $3$ $4$ as liike directed spanning  tree.

so answer will be $4!$​​​​​​ i.e. no of dirferent arrangements of non root node

---

number of such directed spanning trees rooted at vertex any other than 5= $0$.

Answer 1

Method 1(Complete Analysis) :

Directed Spanning Tree definition is given. From the definition, it can be seen that Directed Spanning Tree(DST) is basically a Directed Acyclic Graph(DAG) whose root node is $5,$ and it contains all the vertices. We need to find how many such DAGs are possible. Let’s find out :

$5$ is the root node of the DAG. Let’s fix this at one place and permute all other numbers.

$5, 4, 3, 1, 2$ is one permutation possible, Similarly $5, 3, 4, 1, 2$ is other permutation possible.

Total there are $4! = 24$ permutations possible.

Now you give me any permutation (where $5$ is fixed at start) and I will give you corresponding DAG.
I will use one idea – $\color{blue}{ \text{ Connect a node to the nearest larger node on its left side. } }$ 

For example, you give me $5, 3, 4, 1, 2$ as permutation then i will draw following DAG.

For $3$, nearest larger node on the left is $5$.
For $4$, nearest larger node on the left is $5$.
For $1$, nearest larger node on the left is $4$.
For $2$, nearest larger node on the left is $4$.

In this way, we can say that for every permutation there is $\color{red}{\text{unique }}$DAG.

Now, we can say number of DAGs is atleast as large as number of permutations. Maybe more DAGs than $4!$?

Can we have unique permutation for any given DAG ? – if yes then there is bijection between set of DAGs possible and the set of permutations possible,  And So answer will be $4!$.

Before that first understand that these 2 DAGs are the same – 

it does not matter if you swap left or right subtrees because they(Question makers) are interested in subgraphs and both the DAGs above are the same subgraph.

Now you give me a DAG, I will arrange all siblings of a node in increasing order(from left to right) and then I will take level order traversal to write permutation. For example, You give me the following DAG – 

 

I will rearrange nodes as following – 

Level order will be  $5, 1, 4, 2, 3$

Now if we try to draw a DAG using same permutation, you will find same DAG.

For $1$, nearest larger node on the left is $5$.
For $4$, nearest larger node on the left is $5$.
For $2$, nearest larger node on the left is $4$.
For $3$, nearest larger node on the left is $4$.

Both DAGs are the same.

Now it does not matter how I am converting a DAG to permutation or permutation to DAG. Consider my method as blackbox, I have some definite rule as blackbox and I can convert to each other uniquely.

So, we have shown that There is a bijection between set of DAGs possible and the set of permutations possible, Hence, answer will be $4!.$

---

Method 2 (Counting based on number of levels) : Will be added soon.

Comments

But where it is said that the tree should be binary tree?

Answer 2

Sachin sir’s illuminating ans has  been an eye opener, Lemme add another perspective which might be the “level” based approach.

 Construction:

1. Level 0 corresponds to the source/root node in DAG.
2. If a node $j$ is atmost $L$ edges away from our source/root node, we keep node $j$ at Level $L$, or we’ll be having 1 node per level to comply with the given definition of our graph.
3.  $n-L$^th node will be present at Level L.
4. There’re $L$ independent choices to connect $n-L$ ^th node with $L-1$ nodes in level $L-1$ or equivalently there’re $L$ edges to coming from $L-1$^th level to $L$^th level.
5. We’re constructing a Spanning Tree in a top-down approach, wherein, if we’re at level $L$, we assume that all the L nodes in level $L-1$ has been connected in a DAG.

Here’s a diagrammatic view of this recursive structure:

In the given problem

(Node=4,Level=1)→ 1 (only one way to connect 4 to 4)

(Node=3,Level=2)→ 2 ( 3 can have an incoming edge from either 4 or 5)

(Node=2,Level=3)→ 3 ( 2 can have an incoming edge from either 3,4 or 5)

(Node=1,Level=4)→ 4 ( 1 can have an incoming edge from either 2,3,4 or 5)

As the choices are independent in nature, and connecting all the levels maps to a different spanning tree or we’ve $4! = 4*3*2*1=24$ Spanning Trees.

More Generally, if we denote C(L) to be number of spanning trees in a $L$ level structure, we can have the following recurrence relation:-

C(L)= L*C(L-1), which is nothing but L! assuming the root node is at level 0.

 

 

 

 

 

 

Answer 3

If no. of vertices are 5 then (n-1) edges will be there so ( 5-1) = 4 edges 

then, 4! = 24 .