◀ ▲ ▶Branches / Graph-theory / Definition: Digraph, Initial and Terminal Vertices, Loops, Parallel and Inverse Edges, Simple Digraph

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:

Table of Contents

Examples: 1

Mentioned in:

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