Graph Terminology II

Cycles

A cycle is similar to a path, except that its first and last nodes are identical. In other words, a cycle is like a path that loops back into itself.

The following example graph shows the cycle $a \to c \to d \to a$ marked in blue.

In an undirected graph, a single edge between nodes $u$ and $v$ consists of the two “half-edges” $(u, v)$ and $(v, u)$. However, the walk $u \to v \to u$, forward and backward along the edge is not considered a cycle.

In general, in an undirected cycle, each undirected edge may only be traversed once. This also means that an undirected cycle needs to be at least of length three, while a directed cycle can be of length two.

A graph that contains at least one cycle is called cyclic, and a graph that does not contain any cycle is called acyclic.

Reachability

If there is a path from node ...