in Algorithms retagged by
3,213 views
11 votes
11 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 retagged by
by
3.2k views

3 Answers

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

edited by

1 comment

But where it is said that the tree should be binary tree?
0
0
8 votes
8 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.

 

 

 

 

 

 

0 votes
0 votes

The adjacency matrix representation will look like this of the above specified rule.

Now started from 5 as a root we need to have a directed spanning tree and need to calculate such total spanning trees possible.

Now see if you choose any vertex and start to traverse the graph you will find there is no cycle formation.

But what does it signify? for the very best part we can now calculate the number of spanning trees easily.

So, 5 as a root of spanning tree we can calculate the total spanning trees by selecting the vertex with most outgoing edges and creating a permutation of them.

starting from 5: 4 outgoing edges therefore 4 possibilities.

now out of 1,2,3,4, vertex 4 has most outdegrees. Total outdegrees  = 3, therefore possibilities = 3

now out of 1,2,3, vertex 3 has most outdegrees. Total outdegrees = 2, therefore possibilities = 2

and out of 1 and 2, 2 has one outdegree. Total outdegrees = 1 

 

Therefore total possibilities = 4*3*2 = 24

Hence, 24 spanning trees are possible.


But why everytime max outdegree vertex is chosen? 

Let’s say we are only working for three vertex. 1,2 and 3

now the max directed spanning tree possible would be equal to 2 and these 2 cases will only be the cases [with 3 as starting vertex] where spanning tree is possible. 

ago
Answer:

Related questions