Combinatorial Approach
In Sect. 3.2, we already addressed the Strahler analysis of trees and other networks. Vannimenus and Viennot [222] extend this subject with the goal to find a combinatorial mechanism for the production of branching structures. Here, a randomly controlled algorithm is applied as well, though, in contrast to earlier procedures, the basis is a complex statistical model.
With this method, the problem of having to define the appearance of the tree by exclusively using local rules is at least partially circumvented. Here, a mechanism allows for the topological modification of the entire tree, which was only possible to some extent with the previous methods.
For describing a branching structure, the Strahler analysis assigns to each node and to each edge in a tree a number: their order (Horton-Strahler index). Viennot et al. extend this enumeration to a biorder that stores a number pair (c, d) per node. If к is the Strahler order of the father and i and j those of the sons, then we define:
|
Strahler analysis |
|
c = к, d = i c = d = к — 1 |
|
if j = к and i < к else (i = j = к — 1). |
|
Hence, the biorder represents a measure for the node which incorporates the order of the sons. Here, the parameter c always contains the larger of the two Strahler values, and d the smaller one. We obtain a measure for the type of branching, and for the structure of the attached subtree correlating to the Strahler order, respectively. In the next step, for all nodes with a Strahler number the probability that they have a certain biorder is computed. These probabilities are stored in the lines of the branching matrix P. Values are calculated one by one for the tree: |
|
biorder |
|
■ ak Number of nodes with Horton-Strahler order к к > 2 ■ bk, i Number of nodes with biorder (к, ї) 1 < i < к ■ bk, k Number of nodes with biorder (к — 1,к — 1) к > 2 |
The thus generated branching matrices display characteristic forms for various types of trees. A perfectly branched binary tree uses the following branching matrix (the first line with p1t1 = 1 is omitted in each case):
|
|
 |
|
|
|
Random binary trees that contain n nodes do have, statistically, for a larger number of nodes the following branching matrix:
1/8
1/16 1/16
. . ...
|
Self-similar branching structures, such as the already discussed ferns that are found in Sect. 3.3, have equal lines based on the definition of the biorder that are shifted one column to the right.
To simulate a branching structure, a binary tree Tn with Strahler number S is generated from a given triangular (s - 1) x s branching matrix P and a given S < s via a random process. The resulting branching matrix is then similar to P. For this purpose the algorithm produces a start tree T1 (which only contains the root edge with the Strahler order S), and step by step the partial trees Tn. Which of the two child edges in Algorithm 4.3 at the point of branching receives the order к and which one the order i is either determined randomly or is defined to be alternating or one-sided.
Algorithm 4.3:
procedure combitree() begin produce T1 n =1 repeat
select terminal edge of Tn with Strahler order к > 1 branch from this edge and assign orders to child edges к and i corresponding to the probability given by the biorder of their edges in the branching matrix
Tn+1 = Tn
until for all terminal edges of Tn+1 we find: к = 1 end
For the construction of the geometry, the branch thickness and the branching angle are computed from the branching order and biorder respectively. The results are not spectacular (see Fig. 4.12), nevertheless this approach deserves attention because of its unique methodology.
