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 arrows, directed edges, directed arcs, or directed lines.
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, arcs, or lines. 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 arrows. More specifically, these entities are addressed as directed multigraphs.
On the other hand, the aforementioned definition allows a directed graph to have loops, but some authors consider a narrower definition that doesn't allow directed graphs to have loops. More specifically, directed graphs without loops are addressed as simple directed graphs, while directed graphs with loops are addressed as loop-digraphs.
Types of directed graphs
Subclasses
Symmetric directed graphs are directed graphs where all edges are bidirected.
Simple directed graphs are directed graphs that have no loops 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 arrows. It follows that a complete digraph is symmetric.
* Oriented graphs are directed graphs having no bidirected edges. It follows that a directed graph is an oriented graph if and only if it hasn't any 2-cycle.
** Tournaments are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs.
** Directed acyclic graphs are directed graphs with no directed cycles.
*** Multitrees are DAGs in which no two directed paths from a single starting vertex meet back at the same ending vertex.
*** Oriented trees or polytrees are DAGs formed by orienting the edges of undirected acyclic graphs.
**** Rooted trees are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root.
Digraphs with supplementary properties
Weighted directed graphs are directed graphs with weights assigned to their arrows, similarly to weighted graphs.
* Flow networks are weighted directed graphs where two nodes are distinguished, a source and a sink.
Rooted directed graphs are digraphs in which a vertex has been distinguished as the root.
* Control flow graphs are rooted digraphs used in computer science as a representation of the paths that might be traversed through a program during its execution.
Signal-flow graphs are directed graphs in which nodes represent system variables and branches represent functional connections between pairs of nodes.
Flow graphs are digraphs associated with a set of linear algebraic or differential equations.
Commutative diagrams are digraphs used in category theory, where the vertices represent objects and the arrows represent morphisms, with the property that all directed paths with the same start and endpoints lead to the same result by composition.
In the theory of Lie groups, a quiverQ is a directed graph serving as the domain of, and thus characterizing the shape of, a representationV defined as a functor, specifically an object of the functor category FinVctKF where F is the free category on Q consisting of paths in Q and FinVctK is the category of finite-dimensional vector spaces over a fieldK. Representations of a quiver label its vertices with vector spaces and its edges compatibly with linear transformations between them, and transform via natural transformations.
Basic terminology
An arrow is considered to be directed fromxtoy; y is called the head and x is called the tail of the arrow; y is said to be a direct successor of x and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. The arrow is called the inverted arrow of. The adjacency matrix of a multidigraph with loops is the integer-valued matrix with rows and columns corresponding to the vertices, where a nondiagonal entry aij is the number of arrows from vertex i to vertex j, and the diagonal entry aii is the number of loops at vertex i. The adjacency matrix of a directed graph is unique up to identical permutation of rows and columns. Another matrix representation for a directed graph is its incidence matrix. See direction for more definitions.
Indegree and outdegree
For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex and the number of tail ends adjacent to a vertex is its outdegree. Let and. The indegree of v is denoted deg− and its outdegree is denoted deg+. A vertex with is called a source, as it is the origin of each of its outcoming arrows. Similarly, a vertex with is called a sink, since it is the end of each of its incoming arrows. The degree sum formula states that, for a directed graph, If for every vertex,, the graph is called a balanced directed graph.
Degree sequence
The degree sequence of a directed graph is the list of its indegree and outdegree pairs; for the above example we have degree sequence,,, ). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence. The directed graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positive integer pairs. A sequence which is the degree sequence of some directed graph, i.e. for which the directed graph realization problem has a solution, is called a directed graphic or directed graphical sequence. This problem can either be solved by the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem.
A directed graph is weakly connected if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph. A directed graph is strongly connected or strong if it contains a directed path from x to y and a directed path from y to x for every pair of vertices. The strong components are the maximal strongly connected subgraphs.
