In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

Definition

In formal terms, a directed graph is an ordered pair where

V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Directed graph

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, links or lines.

Directed graph

The aforementioned definition does not allow a directed graph to have multiple arrows with the same source and target nodes, but some authors consider a broader definition that allows directed graphs to have such multiple arcs (namely, they allow the arc set to be a multiset). Sometimes these entities are called directed multigraphs (or multidigraphs). On the other hand, the aforementioned definition allows a directed graph to have loops (that is, arcs that directly connect nodes with themselves), but some authors consider a narrower definition that does not allow directed graphs to have loops. Directed graphs without loops may be called simple directed graphs, while directed graphs with loops may be called loop-digraphs (see section Types of directed graph).

Directed graph

Types of directed graphs

Subclasses

Symmetric directed graphs are directed graphs where all edges appear twice, one in each direction (that is, for every arrow that belongs to the digraph, the corresponding inverse arrow also belongs to it). (Such an edge is sometimes called "bidirected" and such graphs are sometimes called "bidirected", but this conflicts with the meaning for bidirected graphs.) Simple directed graphs are directed graphs that have no loops (arrows that directly connect vertices to themselves) and no multiple arrows with same source and target nodes. As already introduced, in case of multiple arrows the entity is usually addressed as directed multigraph. Some authors describe digraphs with loops as loop-digraphs. Complete directed graphs are simple directed graphs where each pair of vertices is joined by a symmetric pair of directed arcs (it is equivalent to an undirected complete graph with the edges replaced by pairs of inverse arcs). It follows that a complete digraph is symmetric. Semicomplete multipartite digraphs are simple digraphs in which the vertex set is partitioned into sets such that for every pair of vertices x and y in different sets, there is an arc between x and y. There can be one arc between x and y or two arcs in opposite directions. Semicomplete digraphs are simple digraphs where there is an arc between each pair of vertices. Every semicomplete digraph is a semicomplete multipartite digraph in a trivial way, with each vertex constituting a set of the partition. Quasi-transitive digraphs are simple digraphs where for every triple x, y, z of distinct vertices with arcs from x to y and from y to z, there is an arc between x and z. There can be just one arc between x and z or two arcs in opposite directions. A semicomplete digraph is a quasi-transitive digraph. There are extensions of quasi-transitive digraphs called k-quasi-transitive digraphs. Oriented graphs are directed graphs having no opposite pairs of directed edges (i.e. at most one of and may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it has no 2-cycle. (This is not the only meaning of "oriented graph"; see Orientation (graph theory).) Tournaments are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs. A tournament is a semicomplete digraph. A directed graph is acyclic if it has no directed cycles. The usual name for such a digraph is directed acyclic graph (DAG). Multitrees are DAGs in which there are no two distinct directed paths from the same starting vertex to the same ending vertex. Oriented trees or polytrees are DAGs formed by orienting the edges of trees (connected, acyclic undirected graphs). Rooted trees are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root (they are called, respectively, arborescences or out-trees, and in-trees.