# Definition:Directed Graph

## Contents

## Informal Definition

A **directed graph** or **digraph** is a graph each of whose edges has a **direction**:

In the above graph, the vertices are $A, B, C$ and $D$.

### Arc

Let $G = \left({V, E}\right)$ 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 $AB, BD, DC, DA$ and $AD$.

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.

Thus the above **digraph** can be defined as:

- $D = \struct {V, E}: V = \set {A, B, C, D}, E = \set {\tuple {A, B}, \tuple {B, D}, \tuple {D, C}, \tuple {D, A}, \tuple {A, D} }$

## 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 asymmetric, then $D$ is called a **simple digraph**.

That is, in a simple digraph there are no pairs of arcs (like there are between $A$ and $D$ in the diagram above) which go in both directions between two vertices.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 1.5$: Directed Graphs as Mathematical Models - 2010: Steve Awodey:
*Category Theory*(2nd ed.) ... (previous) ... (next): $\S 1.7$ - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**directed graph**