More Terminology

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 non-zero length in which . The length of a cycle is just the length of the path P.
• A loop  is a cycle of length one. That is, 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.