The main theme of this chapter is acyclicity. A connected graph with no cycle is a tree. There are several ways to visit the vertices of a tree. More generally, if a digraph has no cycle, then its vertices may be ordered in such a way that if (a, b) is an edge, then the index associated with a is less than the one associated with b. This ordering is called a topological sort.

4.1. Trees

In this section, we consider only unoriented graphs. Directed trees will only be considered in section 8.6. Trees are ubiquitous in computer science to manipulate various forms of data. As an example, when considering formal grammar, we associate with a string, a parse tree (or derivation tree) according to the rules of the grammar used to build the string.

The tree depicted in Figure 4.1 permits one to associate a value with an expression to be computed. To that end, we have to properly traverse the tree (see postorder traversal below).

DEFINITION 4.1 (Tree).– A tree is a simple connected acyclic graph. Asimple graph whose connected components are trees^{1} is a forest. A rooted tree is a pair (G, v_{0}) where G is a tree and v_{0}is a vertex of G. In that case, a vertex u has level (or height) k when d(v_{0}, u) = k. This naturally induces an orientation of the edges from vertices of level ℓ to adjacent vertices ...

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