Orientation of a graph

Orientation of a graph --- ориентация графа.

Let [math]\displaystyle{ G = (V,E) }[/math] be a finite undirected graph. Then [math]\displaystyle{ G' = (V,E') }[/math] is an orientation of a graph [math]\displaystyle{ G }[/math] if for all [math]\displaystyle{ (x,y) \in E }[/math] [math]\displaystyle{ E' }[/math] contains the arc [math]\displaystyle{ (x,y) }[/math] or [math]\displaystyle{ (y,x) }[/math]. [math]\displaystyle{ G' }[/math] is a transitive orientation of [math]\displaystyle{ G }[/math] if [math]\displaystyle{ E' }[/math] is transitive as a binary relation on [math]\displaystyle{ V }[/math]. An acyclic orientation of a digraph [math]\displaystyle{ G = (V,E) }[/math] is an acyclic digraph [math]\displaystyle{ \vec{G} = (v, \vec{E}) }[/math] such that [math]\displaystyle{ \vec{E} \subseteq E }[/math].

An orientation [math]\displaystyle{ D }[/math] of [math]\displaystyle{ G }[/math] is strong if any pair of vertices in [math]\displaystyle{ D }[/math] are mutually reachable in [math]\displaystyle{ D }[/math]. Given a 2-edge-connected graph, let [math]\displaystyle{ {\mathcal D}(G) }[/math] be the set of all strong orientations of [math]\displaystyle{ G }[/math]. The orientation number of [math]\displaystyle{ G }[/math] is defined to be [math]\displaystyle{ \vec{d}(G) = \min \{d(D)\;| \; D \in {\mathcal D}(G)\} }[/math]. The problem of evaluating the orientation number of an arbitrary connected graph is very difficult.