Definition:Digraph/Formal Definition

Definition

A directed graph or digraph $D$ is a non-empty set $V$ together with an antireflexive relation $E$ on $V$.

The elements of $E$ are the arcs.

Thus the above digraph can be defined as:

$D = \struct {V, E}:$

$V = \set {v_1, v_2, v_3, v_4}$

$E = \set {\tuple {v_1, v_2}, \tuple {v_2, v_4}, \tuple {v_4, v_3}, \tuple {v_4, v_1}, \tuple {v_1, v_4} }$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.5$: Directed Graphs as Mathematical Models
• 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees: Directed Graphs