# Definition: Digraph, Initial and Terminal Vertices, Loops, Parallel and Inverse Edges, Simple Digraph

A digraph or directed graph $$D$$ is a quadruple $$D:=(V,E,\alpha,\omega)$$ with the following properties:

1. $$V$$ is a non-empty set of elements called vertices or nodes.
2. $$E$$ is a set (non-empty or empty) of elements, called edges or arcs.
3. Vertices and edges are not the same objects, formally $$V\cap E=\emptyset$$.
4. The map $$\alpha: E\mapsto V$$, assigns to every edge $$e$$ its initial vertex, denoted by $$\alpha(e)$$.
5. The map $$\omega: E\mapsto V$$ assigns to every edge $$e$$ its terminal vertex, denoted by $$\omega(e)$$.

If $$\alpha(e)=\omega(e)$$, the edge $$e$$ is called a loop.

Two edges $$e$$ and $$e'$$ are called parallel or multiple edges if $$\alpha(e)=\alpha(e')$$ and $$\omega(e)=\omega(e')$$, (thus they have the same initial and terminal vertices).

Two edges $$e$$ and $$e'$$ are called inverse if $$\alpha(e)=\omega(e')$$ and $$\omega(e)=\alpha(e')$$, (thus the intial vertex of the first edge is the terminal vertex of the second edge and vice versa).

We call $$D$$ a simple digraph if it has no loops and no parallel edges.

#### Example digraph:

Examples: 1

Algorithms: 1 2
Chapters: 3
Corollaries: 4 5
Definitions: 6 7 8 9 10 11 12 13 14 15
Examples: 16 17
Explanations: 18
Proofs: 19 20

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition