in Algorithms edited by
1,787 views
5 votes
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 __________________.
in Algorithms edited by
by
1.8k views

2 Answers

6 votes
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.

selected by
4 votes
4 votes

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:

Related questions