I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes

1,2,3,4 then it is given that the number of ordered trees is 5. How come this is true. I can create the following trees. Lets suppose the root is 1

  1            1          1          1
| | |        | | |      | | |      | | |
2 3 4        3 2 4      4 2 3      2 4 3

 1   1
 |   | 
 2   3 
 |   |
 3   2
 |   |
 4   4

and the list goes on. I didn't understand this part. For oriented trees, I can say that the first four trees are equivalent and same and the bottom two trees are equali

  • $\begingroup$ According to Cayley's formula, the number of oriented trees on $n$ vertices is $n^{n-1}$ (this is $n$ times the number given by the formula, since there are $n$ choices for the root). The number of ordered trees is surely larger. $\endgroup$ – Yuval Filmus Aug 28 '12 at 22:13

Ordered Tree

A tree where the children of each node have a designated order (not necessarily based on their value) and can be referred to specifically.

Oriented Tree

A tree used to represent hierarchical data. All edges are directed outward from a distinguished root node. also we can say,that oriented tree may contains at most undirected path between vertex,as in the following statment

A polytree or oriented tree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either.

  • 1
    $\begingroup$ It might be more helpful to explain more details instead of only the definitions. $\endgroup$ – Gigili May 5 '12 at 14:08
  • $\begingroup$ ok i see thanks for advice $\endgroup$ – dato datuashvili May 5 '12 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.