Analysis of Complex Networks

17.2 Trees

Trees are a fundamental object in graph theory and combinatorics as well as a basic object for data structures and algorithms in computer science. In recent years research related to (random) trees has been constantly increasing and several asymptotic and probabilistic techniques have been developed to describe characteristics of interest of large trees in different settings.

A basic class of rooted trees are planted plane trees. Starting from the root, every node has an arbitrary number of successors with a natural left to right order (Figure 17.1). In particular, the subtrees of the root vertex are again planted plane trees.

This example is also very instructive in order to give a flavor of analytic combinatorics. Let P denote the set of planted plane trees. Then from the above description we obtain the recursive relation

Figure 17.1 Planted plane tree.

(see again the schematic Figure 17.1). With the GF

this translates to

Hence

and consequently

Note that z₀ = 1/4 is the ...