Hi I understand that for rooted tree, the definition is as follow:

  1. Is a directed graph $D=<V,E>$
  2. $\exists v\in V\rightarrow \deg^-(v)=0$ which indicate the in-degree of $v$ is $0$
  3. $\forall v'\in(V/\{v\})\rightarrow\deg^-(v')=1$ which indicate the in-degree of nodes other than $v$ is $1$

I understand that an ordered tree is based on a rooted tree, which all sub-nodes of any node have an order. But I cannot find a formal mathematical expression for this.

May I ask how should I define it with formal mathematical expression??


1 Answer 1


Let $T$ be such a tree and let us write $xTy$ for the unique path in $T$ between vertices $x$ and $y$. Let us denote $r$ as the root vertex in $T$.

We can impose a partial ordering on $V(T)$ by letting $x \leq y$ if $x \in rTy,\ \forall x,y \in V(T)$. In such a structure every leaf node is a maximal element of $T$.

Here is an example, generated via sage:

enter image description here

However, we can endow our tree structure with different orderings, e.g. horizontal orderings. Have a look on this exemplary collection of different partial orderings for rooted trees on wikipedia.

  • $\begingroup$ Thanks a lot!!!! May I further ask that does $V(T)$ impose the vertex set of the tree $T$ $\endgroup$
    – Shore
    Feb 22, 2021 at 3:44
  • $\begingroup$ And $x\in rTy$ impose that x is a vertex that in path $rTy$ ?? $\endgroup$
    – Shore
    Feb 22, 2021 at 3:49
  • $\begingroup$ $V(T)$ is just a different notation for referring to the vertex set of $T$ if one have not written $T=(V,E)$. $x \in rTy$ means that $x$ is in the path $rTy$. $\endgroup$ Feb 22, 2021 at 8:27

You must log in to answer this question.

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