Inmathematics, and more specifically ingraph theory, adirected graph (ordigraph) is agraph that is made up of a set ofvertices connected by directededges, often calledarcs.
A is a set ofordered pairs of vertices, calledarcs,directed edges (sometimes simplyedges with the corresponding set namedE instead ofA),arrows, ordirected lines.
It differs from an ordinary orundirected graph, in that the latter is defined in terms ofunordered pairs of vertices, which are usually callededges,links orlines.
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 amultiset). Sometimes these entities are calleddirected multigraphs (ormultidigraphs). On the other hand, the aforementioned definition allows a directed graph to haveloops (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.[2]Directed graphs without loops may be calledsimple directed graphs, while directed graphs with loops may be calledloop-digraphs (see sectionTypes of directed graph).
A simple directed acyclic graphA tournament on 4 vertices
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 forbidirected graphs.)
Simple directed graphs are directed graphs that have noloops (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 asdirected multigraph. Some authors describe digraphs with loops asloop-digraphs.[2]
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 undirectedcomplete 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 verticesx andy in different sets, there is an arc betweenx andy. There can be one arc betweenx andy or two arcs in opposite directions.[3]
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.[4]
Quasi-transitive digraphs are simple digraphs where for every triplex,y,z of distinct vertices with arcs fromx toy and fromy toz, there is an arc betweenx andz. There can be just one arc betweenx andz or two arcs in opposite directions. A semicomplete digraph is a quasi-transitive digraph. There are extensions of quasi-transitive digraphs calledk-quasi-transitive digraphs.[5]
Oriented graphs are directed graphs having no opposite pairs of directed edges (i.e. at most one of(x,y) and(y,x) may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it has no2-cycle.[6] Such a graph can be obtained by applying anorientation to an undirected graph.
Tournaments are oriented graphs obtained by choosing a direction for each edge in undirectedcomplete graphs. A tournament is a semicomplete digraph.[4]
Multitrees are DAGs in which there are no two distinct directed paths from the same starting vertex to the same ending vertex.
Oriented trees orpolytrees 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 orout-trees, andin-trees.
Weighted directed graphs (also known asdirected networks) are (simple) directed graphs withweights assigned to their arrows, similarly toweighted graphs (which are also known as undirected networks orweighted networks).[2]
Flow networks are weighted directed graphs where two nodes are distinguished, asource and asink.
Rooted directed graphs (also known asflow 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 (edges, arcs, or arrows) 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 incategory theory, where the vertices represent (mathematical) 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 ofLie groups, aquiverQ is a directed graph serving as the domain of, and thus characterizing the shape of, arepresentationV defined as afunctor, specifically an object of thefunctor category FinVctKF(Q) whereF(Q) is thefree category onQ consisting of paths inQ and FinVctK is the category of finite-dimensionalvector spaces over afieldK. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly withlinear transformations between them, and transform vianatural transformations.
Oriented graph with corresponding incidence matrix
An arc(x,y) is considered to be directedfromxtoy;y is called thehead andx is called thetail of the arc;y is said to be adirect successor ofx andx is said to be adirect predecessor ofy. If apath leads fromx toy, theny is said to be asuccessor ofx andreachable fromx, andx is said to be apredecessor ofy. The arc(y,x) is called thereversed arc of(x,y).
Theadjacency matrix of a multidigraph with loops is the integer-valuedmatrix with rows and columns corresponding to the vertices, where a nondiagonal entryaij is the number of arcs from vertexi to vertexj, and the diagonal entryaii is the number of loops at vertexi. The adjacency matrix of a directed graph is alogical matrix, and isunique up to permutation of rows and columns.
Another matrix representation for a directed graph is itsincidence matrix.
A directed graph with vertices labeled (indegree, outdegree)
For a vertex, the number of head ends adjacent to a vertex is called theindegree of the vertex and the number of tail ends adjacent to a vertex is itsoutdegree (calledbranching factor in trees).
LetG = (V,E) andv ∈V. The indegree ofv is denoted deg−(v) and its outdegree is denoted deg+(v).
A vertex withdeg−(v) = 0 is called asource, as it is the origin of each of its outgoing arcs. Similarly, a vertex withdeg+(v) = 0 is called asink, since it is the end of each of its incoming arcs.
Thedegree sum formula states that, for a directed graph,
If for every vertexv ∈V,deg+(v) = deg−(v), the graph is called abalanced directed graph.[8]
The degree sequence of a directed graph is the list of its indegree and outdegree pairs; for the above example we have degree sequence ((2, 0), (2, 2), (0, 2), (1, 1)). 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.
Thedirected graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positiveinteger pairs. (Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) 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 theKleitman–Wang algorithm or by theFulkerson–Chen–Anstee theorem.
A directed graph isweakly connected (or justconnected[9]) if the undirectedunderlying graph obtained by replacing all directed edges of the graph with undirected edges is aconnected graph.
A directed graph isstrongly connected orstrong if it contains a directed path fromx toy (and fromy tox) for every pair of vertices(x,y). Thestrong components are the maximal strongly connected subgraphs.
A connectedrooted graph (orflow graph) is one where there exists a directed path to every vertex from a distinguishedroot vertex.
^Satyanarayana, Bhavanari; Prasad, Kuncham Syam,Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460,ISBN978-81-203-3842-5;Brualdi, Richard A. (2006),Combinatorial Matrix Classes, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge University Press, p. 51,ISBN978-0-521-86565-4.
