Directed graph

	Email		Print
	Bookmark		Link

Directed graph

A directed graph or digraph is a pair G= (V, A) of:

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

Sometimes a digraph is called a simple digraph to distinguish from the case of directed multigraph, in which the arcs constitute a multiset

Multiset

Discussion

Ask a question about 'Directed graph'

Start a new discussion about 'Directed graph'

Answer questions from other users

Full Discussion Forum

Encyclopedia

A directed graph or digraph is a pair G= (V, A) of:

a set V, whose elements
Element (mathematics)

In mathematics, an element or member of a Set is any one of the distinct objects that make up that set....
are called vertices or nodes,
a set A of ordered pair
Ordered pair

In mathematics, an ordered pair is a collection of two distinguishable objects, one being the first coordinate system , and the other being the second coordinate ....
s of vertices, called arcs, directed edges, or arrows.

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

Sometimes a digraph is called a simple digraph to distinguish from the case of directed multigraph, in which the arcs constitute a multiset

Multiset

In mathematics, a multiset is a generalization of a Set . A Element of a multiset can have more than one Element , while each member of a set has only one membership....
, 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 both loops and multiple arcs in a digraph.

Basic terminology

An arc is considered to be directed from to ; is called the head and is called the tail of the arc; is said to be a direct successor of , and is said to be a direct predecessor of . If a path

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertex such that from each of its vertices there is an edge to the next vertex in the sequence....
made up of one or more successive arcs leads from to , then is said to be a successor of , and is said to be a predecessor of . The arc

(y, x)

is called the arc

(x, y)

inverted.

A directed graph G is called symmetric if, for every arc that belongs to G, the corresponding inverted arc also belongs to G. A symmetric loopless directed graph is equivalent to an undirected graph with the pairs of inverted arcs replaced with edges; thus the number of edges is equal to the number of arcs halved.

The oriented graph, is a graph (or multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes....
) with an orientation or direction assigned to each of its edges. A distinction between a directed graph and an oriented simple graph is that if and are vertices, a directed graph allows both and as edges, while only one is permitted in an oriented graph.

A weighted digraph is a digraph with weights assigned for its arcs, similarly to the weighted graph.

The adjacency matrix

Adjacency matrix

In mathematics and computer science, the adjacency matrix of a finite set directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops at vertex i or just the number o...
of a digraph (with loops and multiple arcs) is the integer-valued matrix

Matrix

Matrix usually refers to:* Matrix , a mathematical object generally represented as an array of numbers;* The Matrix , a series of films, video games and comic books;...
with rows and columns corresponding to the digraph nodes, where a nondiagonal entry is the number of arcs from node i to node j, and the diagonal entry is the number of loops at node i. The adjacency matrix for a digraph is unique up to the permutations of rows and columns.

Another matrix representation for a digraph is its incidence matrix

Incidence matrix

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. 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....
.

See Glossary of graph theory#Direction

Glossary of graph theory

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings....
for more definitions.

Indegree and outdegree

For a node, the number of head endpoints adjacent to a node is called the indegree of the node and the number of tail endpoints is its outdegree.

The indegree is denoted and the outdegree as A vertex with is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with is called a sink.

The degree sum formula states that, for a directed graph

\sum_ \deg^+(v) = \sum_ \deg^-(v) = |A|\, .

Digraph connectivity

A digraph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected graph. It is strongly connected or strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u,v. The strong components are the maximal strongly connected subgraphs.

Classes of digraphs

A directed acyclic graph

Directed acyclic graph

In computer science and mathematics, a directed acyclic graph, also called a DAG, is a with no ; that is, for any Vertex v, there is no nonempty directed path that starts and ends on v....
, occasionally called a dag or DAG, is a directed graph with no directed cycles.

A rooted tree naturally defines a DAG, if all edges of the underlying tree are directed away from the root.

A tournament is an oriented graph obtained by choosing a direction for each edge in an undirected complete graph

Complete graph

In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
.

In the theory of Lie group

Lie group

In mathematics, a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the Differential structure....
s, a quiver

Quiver (mathematics)

In mathematics, a quiver is a directed graph where loops and multiple arrows between two vertex are allowed. They are commonly used in representation theory: a representation, V, of a quiver assigns a vector space V to each vertex x of the quiver and a linear operator V to each arrow a....
Q is a directed graph serving as the domain of, and thus characterizing the shape of, a representation V defined as a functor

Functor

In category theory, a branch of mathematics, a functor is a special type of mapping between categories. Functors can be thought of as morphisms in the category of small categories....
, specifically an object of the functor category

Functor category

In category theory, a branch of mathematics, the functors between two given categories can themselves be turned into a category; the morphisms in this functor category are natural transformations between functors....
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 space

Vector space

File:Vector addition ans scaling.pngA vector space is a mathematical structure formed by a collection of vectors: objects that may be Vector addition together and Scalar multiplication by numbers, called scalar s in this context....
s 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.

Directed graph

Basic terminology

Indegree and outdegree

Digraph connectivity

Classes of digraphs

See also