Definition:Rooted Tree/Branch

From ProofWiki
Jump to: navigation, search

Definition

Let $T$ be a rooted tree with root node $r_T$.

A subset $\Gamma$ of $T$ is a branch if and only if all the following conditions hold:

$(1): \quad$ The root node $r_T$ belongs to $\Gamma$
$(2): \quad$ The parent of each node in $\Gamma \setminus \left\{{r_T}\right\}$ is in $\Gamma$
$(3): \quad$ Each node in $\Gamma$ either:
$(a): \quad$ is a leaf node of $T$
or:
$(b): \quad$ has exactly one child node in $\Gamma$.


Informally, a branch of a rooted tree is the path from the root to a leaf.


Finite

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a branch of $T$.


Then $\Gamma$ is finite if and only if it has exactly one leaf node.


Infinite

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a branch of $T$.


Then $\Gamma$ is infinite if and only if it has no leaf node at the end.


Length

Let $T$ be a rooted tree with root node $r_T$.

Let $\Gamma$ be a finite branch of $T$.


The length of $\Gamma$ is defined as the number of ancestors of the leaf at the end of that branch.


Also see


Sources