2
$\begingroup$

I've been doing some exercises about graph theory and I find myself stuck on this one with no idea of to proceed.

Here's the question :

How many different directed trees can be obtained if we assign all possible orientations to edges of an undirected tree having exactly n nodes ? How many of them will be rooted (directed) trees ?

I started by drawing but there's too many structures possible so I searched through the different formulas and equalities we've learned but can't figure out a way to apply any of them for that question.

Thanks in advance for reading my question and trying to help me.

Yvann

[EDIT] So I just figured something out, simple but yet perfectly answering the question. You have $6$ edges in a $7$ nodes tree. Every edge can be placed in $2$ different directions so you can calculate the number of possible trees easily by writing $2^6 = 64$.
Then to figure out the number of rooted tree is pretty easy, you have $7$ nodes so $7$ possible starting points so $7$ rooted trees within those $64$.

$\endgroup$

1 Answer 1

0
$\begingroup$

I would attack it this way. I'd use the Matrix-Tree Theorem to obtain the number of unrooted spanning trees. You can then apply $n$ orientations to each tree. So by rule of product, multiply your result from the Matrix-Tree Theorem by $n$.

$\endgroup$
5
  • $\begingroup$ That solution would work but the problem is, you don't know which nodes are adjacent so you can't build the adjacent matrix. $\endgroup$ Apr 23, 2014 at 14:54
  • $\begingroup$ Do you at least know how many edges there are? $\endgroup$
    – ml0105
    Apr 23, 2014 at 14:55
  • $\begingroup$ it's a tree so number of edges = number of nodes -1 in my case there's 7 nodes so 6 edges. $\endgroup$ Apr 23, 2014 at 14:56
  • $\begingroup$ I know that. But that doesn't give you a count of the number of spanning trees in $G$. If you are orienting a single spanning tree, there are $n$ such ways to do this. I was asking about the number of edges in $G$. $\endgroup$
    – ml0105
    Apr 23, 2014 at 14:58
  • $\begingroup$ Also, I came across this link on the number of acyclic orientations of a graph: www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf $\endgroup$
    – ml0105
    Apr 23, 2014 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .