Namespaces
Variants
Actions

Difference between revisions of "Graph, oriented"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (links)
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
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''
 
''directed graph''
  
A graph with an orientation assigned to each of its edges. An oriented graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449801.png" /> is specified by a set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449802.png" /> and a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449803.png" /> of ordered pairs of vertices, known as arcs. One says that the arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449804.png" /> issues from the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449805.png" /> and enters the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449806.png" />. The number of arcs issuing from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449807.png" /> is known as the output semi-degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449808.png" />, while the number of arcs entering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g0449809.png" /> is known as the input semi-degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498010.png" />. An alternating sequence of vertices and arcs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498011.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498013.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498014.png" /> to a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498015.png" /> exists, then one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498016.png" /> is reachable from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498017.png" />.
+
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 \{
  
An oriented graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498018.png" /> with numbered vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498019.png" /> and arcs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498020.png" /> can be specified by an [[incidence matrix]], i.e. by the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498021.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498022.png" /> in which
+
\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}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498023.png" /></td> </tr></table>
+
\right .$$
  
The [[adjacency matrix]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498024.png" /> of the vertices of an oriented graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498025.png" /> is the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498026.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498027.png" /> in which the entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498028.png" /> is equal to the number of arcs going from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498029.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498030.png" />. The sums of the elements in the rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498031.png" /> are equal to the output semi-degrees of the vertices of the oriented graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498032.png" />, while the sums of the elements in the columns are equal to the input semi-degrees. An entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498033.png" /> of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498034.png" /> (i.e. the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498035.png" />-th power of the adjacency matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498036.png" />) is equal to the number of sequences of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498037.png" /> going from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498038.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044980/g04498039.png" />.
+
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.
 
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.
Line 15: Line 74:
 
====References====
 
====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>
 
<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====
 
====Comments====

Revision as of 19:42, 5 June 2020


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

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)

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

[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)
How to Cite This Entry:
Graph, oriented. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_oriented&oldid=35937
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article