Directed graphs

A directed graph (digraph) consists of a set of vertices $V$ and a set of ordered pairs of vertices $E$, called directed edges or arcs. Each edge $(u, v)$ starts at vertex $u$ (the tail) and ends at vertex $v$ (the head).

Important properties

• Edges have a direction: $(u, v)$ is different from $(v, u)$.

• A vertex can have incoming edges (in-degree) and outgoing edges (out-degree).

• Directed graphs can have cycles (a path that starts and ends at the same vertex, following the direction of edges).

• A directed graph can have loops (edges from a vertex to itself).