Overview

The terminology in graph theory pretty much explains itself; if it does not, you can read some of the graph theory books suggested in the Appendix. Graphs are important because they are a general way to represent many different types of data and their relationships. Here is a quick review of terms.

A graph is a data structure made up of nodes connected by edges. Edges can be directed (permit travel in only one direction) or undirected (permit travel in both directions). The number of edges entering a node is its indegree; likewise, the number of edges leaving a node is its outdegree. A set of edges that allow you to travel from one node to another is called a path. A cycle is a path that comes back to the node from which it started without crossing itself (this means that a big circle is fine but a figure eight is not).

A tree is a type of directed graph that is important enough to have its own terminology. Its special properties and frequent use have made it important enough to be covered in a separate chapter (chapter 29). The following sections will stress other useful kinds of generalized directed graphs. Generalized directed graphs are classified into nonreconvergent and reconvergent graphs. In a reconvergent graph there are multiple paths between at least one pair of nodes. Reconvergent graphs are either...