Weighted digraph

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

This article or section is missing citations or needs footnotes.
Using inline citations helps guard against copyright violations and factual inaccuracies. (October 2008)

A directed graph.

A directed graph or digraph consists of the following data:

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
two maps from A to V that associate to an arc its head and its tail.

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, rather than a set, of ordered pairs of vertices. Also, in a simple digraph loops, i.e., arcs that pairs of identical elements, are disallowed. On the other hand, some texts allow both loops and multiple arcs in a digraph.

1 Basic terminology
2 Indegree and outdegree
3 Digraph connectivity
4 Classes of digraphs
5 See also
6 References

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

The oriented graph, is a graph (or multigraph) 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 $x$ and $y$ are vertices, a directed graph allows both $(x, y)$ and $(y, x)$ 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 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 $a i j$ is the number of arcs from node i to node j, and the diagonal entry $a i i$ 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) = |E|\, .$

Digraph connectivity

Main article: Connectivity (graph theory)

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 simple directed acyclic graph

A directed acyclic graph, 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 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 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.