Source code online books for professionals by professionals

G
1
 is a forest with two trees. In a tree, nodes with a degree of one are called leaves (or external nodes),
4
 while all others 
are called internal nodes. The larger tree in G
1
, for example, has three leaves and two internal nodes. The smaller tree 
consists of only an internal node, although talking about leaves and internal nodes may not make much sense with 
fewer than three nodes.
Note
 
■
   Graphs with 0 or 1 nodes are called trivial and tend to make definitions trickier than necessary. In many cases, 
we simply ignore these cases, but sometimes it may be important to remember them. They can be quite useful as a  
starting point for induction, for example (covered in detail in Chapter 4).
Trees have several interesting and important properties, some of which are dealt with in relation to specific 
topics throughout the book. I’ll give you a few right here, though. Let T be an undirected graph with n nodes. Then the 
following statements are equivalent (Exercise 2-9 asks you to show that this is, indeed, the case):
 
1.  T is a tree (that is, it is acyclic and connected).
 
2.  T is acyclic and has n–1 edges.
 
3.  T is connected and has n–1 edges.
 
4.  Any two nodes are connected by exactly one path.
 
5.  T is acyclic, but adding any new edge to it will create a cycle.
 
6.  T is connected, but removing any edge yields two connected components.
In other words, any one of these statements of T, on its own, characterizes it as well as any of the others.  
If someone tells you that there is exactly one path between any pair of nodes in T, for example, you immediately know 
that it is connected and has n–1 edges and that it has no cycles.
Quite often, we anchor our tree by choosing a root node (or simply root). The result is called a rooted tree, as opposed 
to the free trees we’ve been looking at so far. (If it is clear from the context whether a tree has a root or not, I will simply use 
the unqualified term tree in both the rooted and free case.) Singling out a node like this lets us define the notions of up and 
down. Paradoxically, computer scientists (and graph theorists in general) tend to place the root at the top and the leaves 
at the bottom. (We probably should get out more …). For any node, up is in the direction of the root (along the single path 
between the node and the root). Down is then any other direction (automatically in the direction of the leaves). Note that 
in a rooted tree, the root is considered an internal node, not a leaf, even if it happens to have a degree of one.
Having properly oriented ourselves, we now define the depth of a node as its distance from the root, while its 
height is the length of longest downward path to any leaf. The height of the tree then is simply the height of the root. 
For example, consider the larger tree in G
1
 in Figure 
C-1
 and let a (highlighted) be the root. The height of the tree is 
then 3, while the depth of, say, c and d is 2. A level consists of all nodes that have the same depth. (In this case, level 0 
consists of a, level 1 of b, level 2 of c and d, and level 3 of e.)
These directions also allow us to define other relationships, using rather intuitive terms from family trees (with 
the odd twist that we have only single parents). Your neighbor on the level above (that is, closer to the root) is your 
parent, while your neighbors on the level below are your children.
5
 (The root, of course, has no parent, and the leaves, 
no children.) More generally, any node you can reach by going upward is an ancestor, while any node you can reach 
by going down is a descendant. The tree spanning a node v and all its descendants is called the subtree rooted at v.
4
As explained later, though, the root is not considered a leaf. Also, for a graph consisting of only two connected nodes, calling 
them both leaves sometimes doesn’t make sense.
5
Note that this is the same terminology as for the in- and out-neighborhoods in digraphs. The two concepts coincide once we start 
orienting the tree edges.

---

AppendIx C 
■
 GrAph TermInoloGy
271
Note
 
■
   As opposed to subgraphs in general, the term subtree usually does not apply to all subgraphs that happen  
to be trees—especially not if we are talking about rooted trees.
Other similar terms generally have their obvious meanings. For example, siblings are nodes with a common 
parent. Sometimes siblings are ordered so that we can talk about the “first child” or “next sibling” of a node, for 
example. In this case, the tree is called an ordered tree.
As explained in Chapter 5, many algorithms are based on traversal, exploring graphs systematically, from some 
initial starting point (a start node). Although the way graphs are explored may differ, they have something in common. 
As long as they traverse the entire graph, they all give rise to spanning trees.
6
 (Spanning trees are simply spanning 
subgraphs that happen to be trees.) The spanning tree resulting from a traversal, called the traversal tree, is rooted at 
the starting node. The details of how this works will be revisited when dealing with the individual algorithms, but graph 
G
4
 in Figure 
C-1
 illustrates the concept. The highlighted subgraph is such a traversal tree, rooted at a. Note that all paths 
from a to the other nodes in the tree follow the edge directions; this is always the case for traversal trees in digraphs.
Note
 
■
   A digraph whose underlying graph is a rooted tree and where all the directed edges point away from the root 
(that is, all nodes can be reached by directed paths from the root) is called an arborescence, even though I’ll mostly talk 
about such graphs simply as trees. In other words, traversal in a digraph really gives you a traversal arborescence.  
The term oriented tree is used about both rooted (undirected) trees and arborescences because the edges of a rooted  
tree have an implicit direction away from the root.
Terminology fatigue setting in yet? Cheer up—only one graph concept left. As mentioned, directed graphs can 
be acyclic, just as undirected graphs can. The interesting thing is that these graphs don’t generally look much like 
forests of directed trees. Because the underlying undirected graph can be as cyclic as it wants, a directed acyclic graph, 
or DAG, can have an arbitrary structure (see Exercise 2-11), as long as the edges point in the right directions—that is, 
they are pointing so that no directed cycles exist. An example of this can be seen in sample graph G
4
.
DAGs are quite natural as representations for dependencies because cyclic dependencies are generally 
impossible (or, at least, undesirable). For example, the nodes might be college courses, and an edge (u,v) would 
indicate that course u was a prerequisite for v. Sorting out such dependencies is the topic of the section on topological 
sorting in Chapter 5. DAGs also form the basis for the technique of dynamic programming, discussed in Chapter 8.
6
This
 
is true only if all nodes can be reached from the start node. Otherwise, the traversal may have to restart in several places, 
 resulting in a spanning forest. Each component of the spanning forest will then have its own root.

---

273