ABSTRACT
In Chapter 8, we considered certain classes of trees that appeal to software engineers
as data structures for the execution of algorithms. In Chapter 10, we looked at some
additional classes of random trees. In the analysis of models based on random graphs,
it is natural to consider trees first, as they are among the simplest of graph structures.
A tree is split into two trees, if an edge is removed, and collapses into a forest of
two or more trees, if a node is removed.1 This decomposition leads naturally to the
formulation of recursion in algorithms, and the corresponding recurrences in their
analysis-action in a large tree follows patterns in smaller subtrees, and accounting
for the effects of the structure when they conjoin to form a larger tree.
