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.