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
In a directed graph, the lines connecting the vertices are called directed edges or arcs.
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 = \left({V, E}\right): V = \left\{{A, B, C, D}\right\}, E = \left\{{\left({A, B}\right), \left({B, D}\right), \left({D, C}\right), \left({D, A}\right), \left({A, D}\right)}\right\}$
Symmetric Digraph
If the relation $E$ in $D$ is also symmetric, then $D$ is called a symmetric digraph.
It follows from the definition of a (simple) graph that a symmetric digraph whose relation $E$ is symmetric is in fact the same thing as an undirected graph.
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
- Gary Chartrand: Introductory Graph Theory (1977): $\S 1.5$
