{{Short description|Assigning directions to the edges of an undirected graph}} [[File:Oriented graph.svg|thumb|The [[directed graph]] (or digraph) on the right is an orientation of the undirected graph on the left]] In [[graph theory]], an '''orientation''' of an [[undirected graph]] is an assignment of a direction to each edge, turning the initial graph into a [[directed graph]].

==Oriented graphs== A directed graph is called an '''oriented graph''' if none of its pairs of vertices is linked by two mutually symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of {{math|(''x'', ''y'')}} and {{math|(''y'', ''x'')}} may be arrows of the graph).<ref>{{citation | last = Diestel | first = Reinhard | contribution = 1.10 Other notions of graphs | edition = 3rd | isbn = 978-3-540-26182-7 | publisher = [[Springer Science+Business Media|Springer]] | title = Graph Theory | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf | year = 2005}}.</ref>

A [[Tournament (graph theory)|tournament]] is an orientation of a [[complete graph]]. A [[polytree]] is an orientation of an undirected [[Tree (graph theory)|tree]].<ref>{{citation | last1 = Rebane | first1 = George | last2 = Pearl | first2 = Judea | author2-link = Judea Pearl | arxiv = 1304.2736 | contribution = The recovery of causal poly-trees from statistical data | pages = 222–228 | title = Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 | year = 1987 }}.</ref> [[Sumner's conjecture]] states that every tournament with {{math|2''n'' − 2}} vertices contains every polytree with {{mvar|n}} vertices.<ref>[http://www.math.uiuc.edu/~west/openp/univtourn.html Sumner's Universal Tournament Conjecture], Douglas B. West, retrieved 2012-08-02.</ref>

The number of [[graph isomorphism|non-isomorphic]] oriented graphs with {{mvar|n}} vertices (for {{math|1=''n'' = 1, 2, 3, …}}) is : 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … {{OEIS|A001174}}. Tournaments are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are [[bijection|bijective]]. Therefore, the same sequence of numbers also solves the [[graph enumeration]] problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.<ref>{{citation | last1 = Harary | first1 = Frank | author1-link = Frank Harary | last2 = Palmer | first2 = Edgar M. | contribution = Formula 5.4.13 | location = New York | mr = 0357214 | page = 133 | publisher = Academic Press | title = Graphical Enumeration | year = 1973}}.</ref>

==Constrained orientations== A [[strong orientation]] is an orientation that results in a [[strongly connected graph]]. The closely related totally cyclic orientations are orientations in which every edge belongs to at least one simple cycle. An orientation of an undirected graph {{mvar|G}} is totally cyclic if and only if it is a strong orientation of every [[connected component (graph theory)|connected component]] of {{mvar|G}}. [[Robbins' theorem]] states that a graph has a strong orientation if and only if it is [[k-edge-connected graph|2-edge-connected]]; disconnected graphs may have totally cyclic orientations, but only if they have no [[bridge (graph theory)|bridges]].<ref>{{citation | last = Robbins | first = H. E. | authorlink = Herbert Robbins | journal = [[The American Mathematical Monthly]] | pages = 281–283 | title = A theorem on graphs, with an application to a problem of traffic control | volume = 46 | issue = 5 | year = 1939 | doi=10.2307/2303897| jstor = 2303897 | hdl = 10338.dmlcz/101517 | hdl-access = free }}.</ref>

An [[acyclic orientation]] is an orientation that results in a [[directed acyclic graph]]. Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint. The [[Gallai–Hasse–Roy–Vitaver theorem]] states that a graph has an acyclic orientation in which the longest path has at most {{mvar|k}} vertices if and only if it can be [[graph coloring|colored]] with at most {{mvar|k}} colors.<ref>{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | contribution = Theorem 3.13 | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | location = Heidelberg | mr = 2920058 | page = 42 | publisher = Springer | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012}}.</ref> Acyclic orientations and totally cyclic orientations are related to each other by [[planar dual]]ity. An acyclic orientation with a single source and a single sink is called a [[bipolar orientation]].<ref>{{citation | last1 = de Fraysseix | first1 = Hubert | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | last3 = Rosenstiehl | first3 = Pierre | author3-link = Rosenstiehl | doi = 10.1016/0166-218X(94)00085-R | issue = 2–3 | journal = Discrete Applied Mathematics | mr = 1318743 | pages = 157–179 | title = Bipolar orientations revisited | volume = 56 | year = 1995| doi-access = free }}.</ref>

A [[transitive orientation]] is an orientation such that the resulting directed graph is its own [[transitive closure]]. The graphs with transitive orientations are called [[comparability graph]]s; they may be defined from a [[partially ordered set]] by making two elements adjacent whenever they are comparable in the partial order.<ref>{{citation | last = Ghouila-Houri | first = Alain | title = Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre | journal = [[Les Comptes rendus de l'Académie des sciences]] | volume = 254 | year = 1962 | pages = 1370–1371 | mr =0172275}}.</ref> A transitive orientation, if one exists, can be found in linear time.<ref>{{citation | last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J. | contribution = Linear-time transitive orientation | title = 8th ACM-SIAM Symposium on Discrete Algorithms | year = 1997 | pages = 19–25}}.</ref> However, testing whether the resulting orientation (or any given orientation) is actually transitive requires more time, as it is equivalent in complexity to [[matrix multiplication]].

An [[Eulerian path|Eulerian orientation]] of an undirected graph is an orientation in which each vertex has equal in-degree and out-degree. Eulerian orientations of [[grid graph]]s arise in [[statistical mechanics]] in the theory of [[ice-type model]]s.<ref>{{citation | last1 = Mihail | first1 = M. | last2 = Winkler | first2 = P. | author2-link = Peter Winkler | doi = 10.1007/s004539900057 | issue = 4–5 | journal = [[Algorithmica]] | mr = 1407581 | pages = 402–414 | title = On the number of Eulerian orientations of a graph | volume = 16 | year = 1996}}.</ref>

A [[Pfaffian orientation]] has the property that certain even-length cycles in the graph have an odd number of edges oriented in each of the two directions around the cycle. They always exist for [[planar graph]]s, but not for certain other graphs. They are used in the [[FKT algorithm]] for counting perfect matchings.<ref>{{citation | last = Thomas | first = Robin | authorlink = Robin Thomas (mathematician) | contribution = A survey of Pfaffian orientations of graphs | contribution-url = http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf | doi = 10.4171/022-3/47 | mr = 2275714 | pages = 963–984 | publisher = Eur. Math. Soc., Zürich | title = International Congress of Mathematicians. Vol. III | year = 2006| volume = 3 | isbn = 978-3-03719-022-7 }}</ref>

==See also== * [[Connex relation]]

==References== {{reflist}}

==External links== *{{mathworld|GraphOrientation|Graph Orientation|mode=cs2}} *{{mathworld|OrientedGraph|Oriented Graph|mode=cs2}}

[[Category:Graph theory objects]]