Graph, oriented

directed graph

A graph with an orientation assigned to each of its edges. An oriented graph $ G $ is specified by a set of vertices $ V $ and a set $ E $ of ordered pairs of vertices, known as arcs. One says that the arc $ ( u , v) $ issues from the vertex $ u $ and enters the vertex $ v $. The number of arcs issuing from $ v $ is known as the output semi-degree of $ v $, while the number of arcs entering $ v $ is known as the input semi-degree of $ v $. An alternating sequence of vertices and arcs $ v _ {0} , e _ {1} , v _ {1} \dots e _ {n} , v _ {n} $ in which $ e _ {i} = ( v _ {i - 1 } , v _ {i} ) $, $ i = 1 \dots n $, is known as an (oriented) sequence. The sequence is closed if its first and last vertices coincide. A path is a sequence in which all vertices are different. A contour is a non-trivial closed sequence (containing at least one arc) in which all vertices, except the first and last ones, are different. If a path from a vertex $ u $ to a vertex $ v $ exists, then one says that $ v $ is reachable from $ u $.

An oriented graph $ G $ with numbered vertices $ v _ {1} \dots v _ {n} $ and arcs $ e _ {1} \dots e _ {m} $ can be specified by an incidence matrix, i.e. by the matrix $ \| b _ {ij} \| $ of dimension $ n \times m $ in which

$$ b _ {ij} = \ \left \{ \begin{array}{rl} + 1 & \textrm{ if } e _ {j} \textrm{ issues from } v _ {i} , \\ - 1 & \textrm{ if } e _ {j} \textrm{ ends at } v _ {i} , \\ 0 & \textrm{ if } e _ {j} \textrm{ is not incident with } v _ {i} . \\ \end{array} \right .$$

The adjacency matrix $ A ( G) $ of the vertices of an oriented graph $ G $ is the matrix $ \| a _ {ij} \| $ of dimension $ n \times n $ in which the entry $ a _ {ij} $ is equal to the number of arcs going from $ v _ {i} $ to $ v _ {j} $. The sums of the elements in the rows of $ A ( G) $ are equal to the output semi-degrees of the vertices of the oriented graph $ G $, while the sums of the elements in the columns are equal to the input semi-degrees. An entry $ ( i, j) $ of the matrix $ A ^ {k} ( G) $ (i.e. the $ k $-th power of the adjacency matrix of $ G $) is equal to the number of sequences of length $ k $ going from $ v _ {i} $ to $ v _ {j} $.

Several types of connectivity can be defined in an oriented graph (cf. Graph, connectivity of a). An oriented graph is said to be strongly connected, or strong, if any two of its vertices are mutually reachable; it is unilaterally connected if, out of any two of its vertices, at least one is reachable from the other; it is weakly connected, or weak, if any two of its vertices are connected by a chain in the graph, such chain having been obtained from the initial oriented graph by replacing each arc by a (non-oriented) edge.

Oriented graphs are used in: probability theory for the representation of a Markov chain; the theory of games in the description of the set of game situations and results of competitions; mathematical economics when solving transportation problems; the theory of automata in constructing transition diagrams, etc. In graph theory itself, an orientation can be introduced in solving certain problems concerning non-oriented graphs, thus reducing the initial problem to a problem on oriented graphs. The basic difference between an oriented and a non-oriented graph is manifested in the definitions of concepts such as a path, connectivity, reachability, distance, etc. The most interesting types of oriented graphs are tournaments (cf. Tournament), transitive graphs, graphs of partial orders, growing trees, graphs of one-place mappings, and contour-free graphs.

Comments

For the terminology in graph theory see also Graph. A contour is better known as a directed cycle. A comprehensive reference for directed (oriented) graphs is [a1].

References

[1]	A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)
[2]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[3]	C.F. Picard, "Graphs and questionnaires" , North-Holland (1980) (Translated from French)
[a1]	F. Harary, R.Z. Norman, D. Cartwright, "Structural models. An introduction to the theory of directed graphs" , Wiley (1965)
[a2]	R.J. Wilson, "Introduction to graph theory" , Longman (1985)