Data Structures and Algorithms
with ObjectOriented Design Patterns in C++
Consider the path
in a directed graph .

Vertex is the successor
of vertex for .
Each element of path P (except the last)
has a successor.

Vertex is the predecessor
of vertex for .
Each element of path P (except the first)
has a predecessor.

A path P is called a simple path if and only if
for all i and j such that .
However, it is permissible for to be the same as
in a simple path.

A cycle is a path P
of nonzero length in which .
The length of a cycle is just the length of the path P.

A loop is a cycle of length one.
I.e., it is a path of the form .

A simple cycle
is a path that is both a cycle and simple.
Referring again to graph in Figure we find that the path
is a simple path of length three.
Conversely, the path also has length three
but is not simple because vertex c occurs twice in the sequence
(but not at the ends).
The graph contains the path which is a cycle of length three,
as well as , a cycle of length four.
The former is a simple cycle but the latter is not.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.