Directed graph

A directed graph or digraph ( directed graph of English ) is a pair with:

• A set of nodes (english vertex / vertices, often called corners)
• A set of ordered pairs of nodes, the directed edges ( engl. directed edge / edges, sometimes called arcs) are called.

A normal or non-directional graph has, in contrast, a disordered quantity of pairs of nodes, which are referred to as non-directional edges.

A directed graph without multiple edges and loops is called a simple digraph (also simple digraph ).

Basic concepts

It is said that a directed edge from to go. Here, the base ( or starting node ) and the head (or end node ) of. Furthermore, considered to be the direct successor and as the direct predecessor of. If results in a graph of after a path is considered as a successor of and acting as a predecessor. The edge is called inverted or inverted edge of.

A directed graph G is called symmetric if G to each edge also contains the corresponding inverted edge. An undirected graph can be easy to convert a symmetric directed graph by replacing each edge directed by the two edges.

In order to obtain the orientation of a simple undirected graph, each edge has to be assigned a direction. Each constructed in this way directed graph is called oriented graph. A simple directed graph may, in contrast to the oriented graph between two nodes contain edges in both directions.

A weighted digraph is a directed graph whose edges are assigned weights, thereby providing an edge- weighted graph. A digraph with weighted edges is known in graph theory as a network.

The adjacency matrix of a digraph ( with loops and multiple edges ) is an integer matrix whose rows and columns correspond to the nodes of the digraph. An entry outside the main diagonal are the number of edges from node i to node j, and the entry of the main diagonal corresponds to the number of loops in the node i The Adjanzenzmatrix a digraph is up to permutation of rows and columns clearly.

A digraph can be represented by an incidence matrix.

Input and output degree

The number of immediate predecessors of a node is referred to as the input level (also inside degrees) and the number of direct descendants the output level (or outside degrees).

The input level of a node in a graph will be referred to with the outer and with degree. A node is with source and a sink node is called. A sink is called universal sink if it has incoming edges of every other node, so if you input level is equal.

For directed graphs, the sum of the input levels is equal to the sum of the output levels, and both of the sum of the directed edges:

If the equation is true for all nodes, the directed graph is called a balanced graph.

Context of digraphs

A directed graph is called weakly connected (or just connected ) if the underlying graph of which is obtained by replacing all directed edges by undirected, a connected graph is. A directed graph is called strongly connected or strong if any two of its nodes are mutually reachable. A maximal strongly connected subgraph of is a strong component.

Representation of directed graphs

Apart from the naive representation of a directed graph by specifying the node and edge set, there are other display options, the so-called edge or node field.

Edge array

An edge field is a representation for directed graphs according to the following scheme:

Wherein the number of nodes, the number of edges and the edges are connected.

Node field

A node field is a representation for directed graphs with the following structure:

Wherein the number of nodes, the number of edges, and the output level of the node is.

Example

Considering as an example the rightmost directed graph, then the edge field and the node field. The bold numbers indicate the output level.

Classes of digraphs

A directed acyclic graph, or acyclic digraph is a directed graph that contains no directed cycle. Special cases of directed acyclic graphs are multiple trees in which all edges ( two directed paths of the graph, emanating from the same starting node, himself may not meet the same end nodes ), oriented trees or Polybäume (orientation of an undirected acyclic graph ) and rooted trees ( oriented trees, of the underlying undirected tree from the root node lead away ).

A tournament graph is an orientation of the complete graph.

Special directed graphs

• Kautz graph