Dark Mode

1,787 views

5 votes

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

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

6 votes

Best answer

**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 same –

it does not matter if you swap left or right subtrees because they(Question makers) are interested in **subgraphs** and above both DAGs are 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 same.

Now it does not matter how I am converting a DAG to perumutation or permutation to DAG. Consider my method as blackbox, I have some definate 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.

4 votes

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

**Construction**:

- Level 0 corresponds to the source/root node in DAG.
- 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.
- $n-L$
^{th}node will be present at Level L. - 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. - 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.