6.1.  Paths and Reachability

Definition 3.7 (Path)

Let G = (V, E, f) be a simple digraph. A sequence of edges is called a path of G, if and only if the terminal node of each edge in the path is the initial node of the next edge, if any, in the path.

An example of such a path:

Definition 3.8 (Length of a Path)

The number of edges appearing in the sequence of a path is called the length of a path.

Definition 3.9 (Cycle)

A path that originates and ends in the same node is called a cycle. A cycle is called simple if no edge in the cycle appears more than once in the path. A cycle is called elementary if it does not traverse through any node more than once.

Definition 3.10 (Acyclic)

A simple digraph that does not have any cycles is called acyclic.

Definition 3.11 (Path Relation)

Let G = (V, E) be a simple digraph. The path relation P of G is defined as

P = { (u,v) | there exists a path from node u to node v }

The path length from the node u to the node v is called the distance and is denoted by d(u, v).

Last modified 22/May/97