Advanced Graph Theory and Combinatorics

4Topological Sort and Graph Traversals

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.

Figure 4.1. A parse tree associated with 4 + 5 + 3 × 7

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. A simple graph whose connected components are trees¹ is a forest. A rooted tree is a pair (G, v₀) where G is a tree and v₀ is a vertex of G. In that case, a vertex u has level (or height) k when d(v₀, u) = k. This naturally induces an orientation of the edges from vertices of level ℓ to adjacent vertices ...