O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

images

Figure 17.1 Planted plane tree.

images

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

images

this translates to

images

Hence

images

and consequently

Note that z0 = 1/4 is the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required