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**.

In formal terms, a directed graph is an ordered pair *G* = (*V*, *A*) where^{ [1] }

*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*.

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*.

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). More specifically, these entities are addressed as ** 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 doesn't allow directed graphs to have loops.^{ [2] } More specifically, directed graphs without loops are addressed as **simple directed graphs**, while directed graphs with loops are addressed as *loop-digraphs* (see section Types of directed graphs).

**Symmetric directed graphs**are directed graphs where all edges are bidirected (that is, for every arrow that belongs to the digraph, the corresponding inversed arrow also belongs to it).**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*.^{ [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 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 partition into partite sets such that for every pair of vertices*x*and*y*in different partite sets, there is an arc between*x*and*y*. Note that there can be one arc between*x*and*y*or two arcs in the 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, where the number of vertices equals the number of partite sets.^{ [4] }**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*. Note that 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.^{ [5] }**Oriented graphs**are directed graphs having no bidirected 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 hasn't any 2-cycle.^{ [6] }**Tournaments**are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs. Note that a tournament is a semicomplete digraph.^{ [7] }**Directed acyclic graphs**(DAGs) are directed graphs with no directed cycles.^{ [8] }*Multitrees*are DAGs in which no two distinct 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 (they are called**out-trees**and**in-trees**, respectively.

**Weighted directed graphs**(also known as**directed networks**) are (simple) directed graphs with*weights*assigned to their arrows, similarly to weighted graphs (which are also known as undirected networks or weighted networks).^{ [2] }**Flow networks**are weighted directed graphs where two nodes are distinguished, a*source*and a*sink*.

**Rooted directed graphs**(also known as**flow 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.**State diagrams**are directed multigraphs that represent finite state machines.**Commutative diagrams**are digraphs used in category 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 of Lie groups, a
**quiver***Q*is a directed graph serving as the domain of, and thus characterizing the shape of, a*representation**V*defined as a functor, specifically an object of the functor category FinVct_{K}^{F(Q)}where*F*(*Q*) is the free category on*Q*consisting of paths in*Q*and FinVct_{K}is the category of finite-dimensional vector spaces over a field*K*. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with linear transformations between them, and transform via natural transformations.

An arc (*x*, *y*) is considered to be directed *from**x**to**y*; *y* is called the *head* and *x* is called the *tail* of the arc; *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 arc (*y*, *x*) is called the *reversed arc* of (*x*, *y*).

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 *a*_{ij} is the number of arcs from vertex *i* to vertex *j*, and the diagonal entry *a*_{ii} 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.

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* (called * branching factor * in trees).

Let *G* = (*V*, *A*) and *v* ∈ *V*. The indegree of *v* is denoted deg^{−}(*v*) and its outdegree is denoted deg^{+}(*v*).

A vertex with deg^{−}(*v*) = 0 is called a *source*, as it is the origin of each of its outcoming arcs. Similarly, a vertex with deg^{+}(*v*) = 0 is called a *sink*, since it is the end of each of its incoming arcs.

The *degree sum formula* states that, for a directed graph,

If for every vertex *v* ∈ *V*, deg^{+}(*v*) = deg^{−}(*v*), the graph is called a *balanced directed graph*.^{ [9] }

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.

The directed graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positive integer 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 the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem.

A directed graph is *weakly connected* (or just *connected*^{ [10] }) 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 from *y* to *x*) for every pair of vertices (*x*, *y*). The *strong components* are the maximal strongly connected subgraphs.

A connected rooted graph (or *flow graph*) is one where there exists a directed path to every vertex from a distinguished *root vertex*.

Wikimedia Commons has media related to . Directed graphs |

- ↑ Bang-Jensen & Gutin (2000). Bang-Jensen & Gutin (2018), Chapter 1.Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
- 1 2 3 Chartrand, Gary (1977).
*Introductory Graph Theory*. Courier Corporation. ISBN 9780486247755. - ↑ Bang-Jensen & Gutin (2018), Chapter 7 by Yeo.
- ↑ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
- ↑ Bang-Jensen & Gutin (2018), Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.
- ↑ Diestel (2005), Section 1.10.
- ↑ Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
- ↑ Bang-Jensen & Gutin (2018), Chapter 3 by Gutin.
- ↑ Satyanarayana, Bhavanari; Prasad, Kuncham Syam,
*Discrete Mathematics and Graph Theory*, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5 ; Brualdi, Richard A. (2006),*Combinatorial Matrix Classes*, Encyclopedia of Mathematics and Its Applications,**108**, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4 . - ↑ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

In mathematics, **graph theory** is the study of *graphs*, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of *vertices* which are connected by *edges*. A distinction is made between **undirected graphs**, where edges link two vertices symmetrically, and **directed graphs**, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In mathematics, particularly graph theory, and computer science, a **directed acyclic graph** is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to sociology to computation (scheduling).

In the mathematical field of graph theory, a **Hamiltonian path** is a path in an undirected or directed graph that visits each vertex exactly once. A **Hamiltonian cycle** is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

In graph theory and computer science, an **adjacency matrix** is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

This is a **glossary of graph theory**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In mathematics, an **incidence matrix** is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is *X* and the second is *Y*, the matrix has one row for each element of *X* and one column for each element of *Y*. The entry in row *x* and column *y* is 1 if *x* and *y* are related and 0 if they are not. There are variations; see below.

In mathematics, and more specifically in graph theory, a **vertex** or **node** is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

In the mathematical field of graph theory, the **distance** between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the **geodesic distance**. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

In mathematics, and, in particular, in graph theory, a **rooted graph** is a graph in which one vertex has been distinguished as the root. Both directed and undirected versions of rooted graphs have been studied, and there are also variant definitions that allow multiple roots.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

A **tournament** is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a directed edge with any one of the two possible orientations.

In the mathematical field of graph theory, the **degree matrix** is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph.

In graph theory and network analysis, indicators of **centrality** identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin. They should not be confused with node influence metrics, which seek to quantify the influence of every node in the network.

In mathematics and computer science, **connectivity** is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In mathematics, and more specifically in graph theory, a **multigraph** is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

In the area of graph theory in mathematics, a **signed graph** is a graph in which each edge has a positive or negative sign.

**Ore's theorem** is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.

In graph theory, a **pseudoforest** is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A **pseudotree** is a connected pseudoforest.

In graph theory, an **ear** of an undirected graph *G* is a path *P* where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of *P* has degree two in *G*. An **ear decomposition** of an undirected graph *G* is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An **open ear decomposition** or a **proper ear decomposition** is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

- Bang-Jensen, Jørgen; Gutin, Gregory (2000),
*Digraphs: Theory, Algorithms and Applications*, Springer, ISBN 1-85233-268-9

(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1-84800-997-6). - Bang-Jensen, Jørgen; Gutin, Gregory (2018),
*Classes of Directed Graphs*, Springer, ISBN 3319718401 . - Bondy, John Adrian; Murty, U. S. R. (1976),
*Graph Theory with Applications*, North-Holland, ISBN 0-444-19451-7 . - Diestel, Reinhard (2005),
*Graph Theory*(3rd ed.), Springer, ISBN 3-540-26182-6 (the electronic 3rd edition is freely available on author's site). - Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965),
*Structural Models: An Introduction to the Theory of Directed Graphs*, New York: Wiley. - Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.