View source for Graph, oriented

<!--
g0449801.png
$#A+1 = 39 n = 0
$#C+1 = 39 : ~/encyclopedia/old_files/data/G044/G.0404980 Graph, oriented,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''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 }  \textrm{ _ } {  } v _ {i} ,  \\
- 1  & \textrm{ if }  e _ {j}  \textrm{ ends }  \textrm{ at }  v _ {i} ,  \\
 0  & \textrm{ if }  e _ {j}  \textrm{ is }   \mathop{\rm not}  \textrm{ incident } \ 
\textrm{ 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|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|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|Tournament]]), transitive graphs, graphs of partial orders, growing trees, graphs of one-place mappings, and contour-free graphs.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Zykov,   "The theory of finite graphs" , '''1''' , Novosibirsk  (1969)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  F. Harary,   "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  C.F. Picard,   "Graphs and questionnaires" , North-Holland  (1980)  (Translated from French)</TD></TR></table>

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F. Harary,   R.Z. Norman,   D. Cartwright,   "Structural models. An introduction to the theory of directed graphs" , Wiley  (1965)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,   "Introduction to graph theory" , Longman  (1985)</TD></TR></table>