# Directed Graph

A directed graph is a graph whose graph edges are all directed graph edges.

## References

### 2013

• (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/directed_graph Retrieved:2013-12-8.
• In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph, or set of nodes connected by edges, where the edges have a direction associated with them. In formal terms, a digraph is a pair $\displaystyle{ G=(V,A) }$ (sometimes $\displaystyle{ G=(V,E) }$) of: [1]
• a set V, whose elements are called vertices or nodes,
• a set A of ordered pairs of vertices, called arcs, directed edges, or arrows (and sometimes simply edges with the corresponding set named E instead of A).

It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges.

Sometimes a digraph is called a simple digraph to distinguish it from a directed multigraph, in which the arcs constitute a multiset, rather than a set, of ordered pairs of vertices. Also, in a simple digraph loops are disallowed. (A loop is an arc that pairs a vertex to itself.) On the other hand, some texts allow loops, multiple arcs, or both in a digraph.

1. . , Section 1.10. , Section 10.

### 2011

• (Sammut & Webb, 2011) ⇒ Claude Sammut (editor), and Geoffrey I. Webb (editor). (2011). “Digraphs.” In: (Sammut & Webb, 2011)
• Synonyms: Directed graphs

Definition: A digraph $\displaystyle{ D }$ consists of a (finite) set of vertices $\displaystyle{ V(D) }$ and a set $\displaystyle{ A(D) }$ of ordered pairs, called arcs, of distinct vertices. An arc $\displaystyle{ (u,\; v) }$ has tail $\displaystyle{ u }$ and head $\displaystyle{ v }$, and it is said to leave $\displaystyle{ u }$ and enter $\displaystyle{ v }$.

Figure 1 shows a digraph $\displaystyle{ D }$ with vertex set $\displaystyle{ V(D)=\{ u,\; v,\; w,\; x,\; y,\;z\} }$ and arc set $\displaystyle{ A(D)=\{ (u, v), (u, w), (v, w), (w, x), (x, w), (x,z), (y, x) (z,x)\} }$. Digraphs can be viewed as generalizations of graphs.

Digraphs, Fig. 1: A digraph.