O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

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

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.

image

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 trees1 is a forest. A rooted tree is a pair (G, v0) where G is a tree and v0 is a vertex of G. In that case, a vertex u has level (or height) k when d(v0, u) = k. This naturally induces an orientation of the edges from vertices of levelto 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.

Start Free Trial

No credit card required