Definition:Digraph
Definition
A digraph is a graph each of whose edges has a direction:
In the above graph, the vertices are $v_1, v_2, v_3$ and $v_4$.
Arc
Let $G = \struct {V, E}$ be a digraph.
The arcs are the elements of $E$.
Informally, an arc is a line that joins one vertex to another.
In the above graph, the arcs are $v_1 v_2, v_2 v_4, v_4 v_3, v_4 v_1$ and $v_1 v_4$.
As can be seen, in this general definition it is allowable for an arc to go in both directions between a given pair of vertices.
Formal 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.
Category-Theoretic Definition
Let $\mathbf {Set}$ be the category of sets.
A digraph is an arrangement of the following form in $\mathbf{Set}$:
- $\begin{xy}
<0em,0em>*{E} = "E", <5em,0em>*{V} = "V",
"E"+/^.3em/+/r1em/;"V"+/^.3em/+/l1em/ **@{-} ?>*@{>} ?*!/_.6em/{s}, "E"+/_.3em/+/r1em/;"V"+/_.3em/+/l1em/ **@{-} ?>*@{>} ?*!/^.6em/{t}, \end{xy}$
Symmetric Digraph
Let $D = \struct {V, E}$ be a digraph such that the relation $E$ in $D$ is symmetric.
Then $D$ is called a symmetric digraph.
Simple Digraph
If the relation $E$ in $D$ is also specifically asymmetric, then $D$ is called a simple digraph.
That is, in a simple digraph there are no pairs of arcs (like there are between $v_1$ and $v_4$ in the diagram above) which go in both directions between two vertices.
Examples
Arbitrary Digraph of Order 6
Let $D = \struct {V, E}$ be a digraph such that:
- $V = \set {v_1, v_2, v_3, v_4, v_5, v_6}$
- $E = \set {\tuple {v_1, v_3}, \tuple {v_2, v_3}, \tuple {v_3, v_4}, \tuple {v_4, v_1}, \tuple {v_4, v_3}, \tuple {v_5, v_6} }$
Then $D$ can be presented in diagram form as:
Also known as
A digraph is also known as a directed graph.
Some sources refer to a digraph as a network, but $\mathsf{Pr} \infty \mathsf{fWiki}$ has a different definition for that.
Also see
- Results about digraphs can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): digraph
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): digraph
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): directed graph