Hi I understand that for rooted tree, the definition is as follow:
- Is a directed graph $D=<V,E>$
- $\exists v\in V\rightarrow \deg^-(v)=0$ which indicate the in-degree of $v$ is $0$
- $\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??
$\endgroup$1 Answer
$\begingroup$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:
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.
$\endgroup$ 3
