Directed graph

Directed graph
A directed graph.

A directed graph or digraph is a pair G = (V,A) (sometimes G = (V,E)) of:[1]

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

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.

Sometimes a digraph is called a simple digraph to distinguish it from a directed multigraph, in which the arcs constitute a multiset, 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 loops, multiple arcs, or both in a digraph.


Basic terminology

An arc e = (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 made up of one or more successive arcs leads from x to y, then y is said to be a successor of x, and x is said to be a predecessor of y. 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.

An orientation of a simple undirected graph is obtained by assigning a direction to each edge. Any directed graph constructed this way is called an oriented graph. A distinction between a simple directed graph and an oriented graph is that if x and y are vertices, a simple directed graph allows both (x,y) and (y,x) as edges, while only one is permitted in an oriented graph.[2][3][4]

A weighted digraph is a digraph with weights assigned for its arcs, similarly to the weighted graph. A digraph with weighted edges in the context of graph theory is called a network.

The adjacency matrix of a digraph (with loops and multiple arcs) is the integer-valued matrix with rows and columns corresponding to the digraph nodes, where a nondiagonal entry aij is the number of arcs from node i to node j, and the diagonal entry aii 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.

See Glossary of graph theory#Direction for more definitions.

Indegree and outdegree

A digraph with vertices labeled (indegree, 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 deg  (v) and the outdegree as deg  + (v). A vertex with deg  (v) = 0 is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with deg  + (v) = 0 is called a sink.

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

\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|\, .

If for every node vV, deg  + (v) = deg  (v), the graph is called a balanced digraph.[5]

Digraph connectivity

A digraph G is called weakly connected (or just connected[6]) if the undirected underlying graph obtained by replacing all directed edges of G with undirected edges is a connected graph. A digraph 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 simple directed acyclic graph

A directed acyclic graph or acyclic digraph is a directed graph with no directed cycles. Special cases of directed acyclic graphs include the multitrees (graphs in which no two directed paths from a single starting node meet back at the same ending node), oriented trees or polytrees (the digraphs formed by orienting the edges of undirected acyclic graphs), and the rooted trees (oriented trees in which all edges of the underlying undirected tree are directed away from the root).

A tournament on 4 vertices

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

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 FinVctKF(Q) where F(Q) is the free category on Q consisting of paths in Q and FinVctK 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.

See also


  1. ^ Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
  2. ^ Diestel (2005), Section 1.10.
  3. ^ Weisstein, Eric W., "Oriented Graph" from MathWorld.
  4. ^ Weisstein, Eric W., "Graph Orientation" from MathWorld.
  5. ^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 9788120338425 ; Brualdi, Richard A. (2006), Combinatorial matrix classes, Encyclopedia of mathematics and its applications, 108, Cambridge University Press, p. 51, ISBN 9780521865654 .
  6. ^ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • directed graph — noun A graph in which the edges are ordered pairs, so that, if the edge (a, b) is in the graph, the edge (b, a) need not be in the graph and is distinct from (a, b) if it is. A directed graph (A,R) is a set of vertices A together with an… …   Wiktionary

  • directed graph — orientuotasis grafas statusas T sritis automatika atitikmenys: angl. directed graph; oriented graph vok. gerichteter Graph, m; orientierter Graph, m rus. орграф, m; ориентированный граф, m pranc. graphe de fluence, m; graphe directe, m; graphe… …   Automatikos terminų žodynas

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph mit Mehrfachkanten — Ein Graph besteht in der Graphentheorie anschaulich aus einer Menge von Punkten, zwischen denen Linien verlaufen. Die Punkte nennt man Knoten oder Ecken, die Linien nennt man meist Kanten, manchmal auch Bögen. Auf die Form der Knoten und Kanten… …   Deutsch Wikipedia

  • Graph ohne Mehrfachkanten — Ein Graph besteht in der Graphentheorie anschaulich aus einer Menge von Punkten, zwischen denen Linien verlaufen. Die Punkte nennt man Knoten oder Ecken, die Linien nennt man meist Kanten, manchmal auch Bögen. Auf die Form der Knoten und Kanten… …   Deutsch Wikipedia

  • Graph automorphism — In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”