A (directed) graph *G*=(*V*, *E*) consists of a set *V* of nodes
and a set *E* of ordered pairs of nodes.
An element is called an edge of the graph.
A graph is *undirected* if for each edge
also holds.
The set
is the set of *predecessors* of a node .
The set
is the set of all *successors* of a node *v*.
The sizes of these sets are
and .

The degree of a node *v* is .

A sequence is a *path* from to
if there are edges for .
A *cycle* is a nonempty path from *v* to *v*.
A graph without cycles is called *acyclic*.
A graph is *dense* if it contains many edges and *sparse* if it
contains only few edges.
It would be superfluously pedantic to define these notions
precisely.
A graph with is always considered
sparse,
while a graph with is always considered
dense.

%

Thu Aug 1 15:27:34 PDT 1996