Sub-branch

MainPage

Definition: A sub-branch of a rooted tree is defined as a set of nodes that joins a ramification or a leaf until the nearest ramification child or root child. The root is defined as being a sub-branch with a single node. Sub-branches that have only one node are called trivial sub-branches.

According to this definition, each node of the rooted tree belongs to one and only one sub-branch, therefore the set composed of all sub-branches of a rooted tree is disjoint and contains all its nodes.

A rooted tree and its sub-branches are illustrated in Figure 1. We can think of each sub-branch as being a single node, and therefore we can build a sub-branch tree, as illustrated in Figure 2. The sub-branch tree is the minimal tree that preserves the same ramifications with the same degrees and ordering as the ramifications of the original tree.

/media/_xsb/iamxt/mxt_def4/GRVIZ90598_001.png

Figure 1. Illustration of sub-branches.

Figure 2. Illustration of the sub-branch tree corresponding to the tree in Figure 1.

In the max-tree, each set of nodes that constitutes a sub-branch represents the variation of a connected component for different threshold values, before it splits in two or more components or before it completely disappears. The number of threshold levels before the connected component represented by the sub-branch splits or completely disappears will be denoted by , and is given by the following equation:

The number of nodes in the sub-branch tree is equal to the number of sub-branches in the original tree and is given by the number of leaves plus the number of ramifications plus one, if the root is not a ramification. Its minimum value is equal . It happens when all leaves are connected directly to the root. Its maximum value happens when the sub-branch tree is almost a full binary tree, except for the root that has only one child. From the theory, the number of nodes in a full binary tree is , since in the sub-branch tree, the root may have only one child, the maximum number of nodes of the sub-branch tree is . Therefore,

The case where the number of nodes in the sub-branch tree is equal to the lower bound is illustrated in Figure 3(a), and the case where the number of nodes in the tree is equal to the upper bound is illustrated in Figure 3(b) .

Figure 3. Illustration of the cases where the number of nodes in the sub-branch tree are equal to (a) and (b).