Paths, cycles, and connectedness

 

Definitions:

A directed walk is a sequence of arcs such that the head of one arc is the tail of the next arc.

The length of a directed walk is the number of arcs in the sequence. A closed directed walk is a directed walk that begins and ends at the same vertex. A directed trail is a directed walk in which no arc is repeated. A directed path is a directed trail in which no vertex is repeated. A directed cycle is a closed directed trail in which no vertices are repeated, except the starting and stopping vertex. Vertex v is reachable from vertex u if there is a directed path from u to v.

The distance from a vertex u to a vertex v in a digraph D is the length of the shortest directed path from u to v. A digraph is strongly connected (or diconnected, or strong) if every vertex is reachable from every other vertex.

A digraph D is weakly connected (or weak) if the underlying graph is connected.

The digraph D is disconnected if the underlying graph is disconnected.

A strong component of a digraph is a maximal subgraph that is strongly connected.

Facts:

1. Using a pencil on a drawing of a digraph, a directed walk can be traversed by following the arrows without lifting the pencil from the graph.

2. Distance in digraphs need not be symmetric. That is, the distance from u to v might be different from the distance from v to u.