# 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**