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 symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of and may be arrows of the graph).
A
tournament is an orientation of a
complete graph. A
polytree
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its ...
is an orientation of an undirected
tree.
Sumner's conjecture
Sumner's conjecture (also called Sumner's universal tournament conjecture) states that every orientation of every n-vertex tree is a subgraph of every (2n-2)-vertex tournament.
David Sumner, a graph theorist at the University of South Carolina ...
states that every tournament with vertices contains every polytree with vertices.
The number of
non-isomorphic oriented graphs with vertices (for ) is
: 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … .
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
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.
Constrained orientations
A
strong orientation is an orientation that results in a
strongly connected graph
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
. 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 is totally cyclic if and only if it is a strong orientation of every
connected component of .
Robbins' theorem states that a graph has a strong orientation if and only if it is
2-edge-connected; disconnected graphs may have totally cyclic orientations, but only if they have no
bridges.
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 vertices if and only if it can be
colored with at most colors. Acyclic orientations and totally cyclic orientations are related to each other by
planar duality. An acyclic orientation with a single source and a single sink is called a
bipolar orientation.
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 graphs; they may be defined from a
partially ordered set by making two elements adjacent whenever they are comparable in the partial order. A transitive orientation, if one exists, can be found in linear time. 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 orientation of an undirected graph is an orientation in which each vertex has equal in-degree and out-degree. Eulerian orientations of
grid graphs arise in
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
in the theory of
ice-type model In statistical mechanics, the ice-type models or six-vertex models are a family of vertex models for crystal lattices with hydrogen bonds. The first such model was introduced by Linus Pauling in 1935 to account for the residual entropy of water ice. ...
s.
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
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, but not for certain other graphs. They are used in the
FKT algorithm for counting perfect matchings.
See also
*
Connex relation
References
External links
*
*{{mathworld, OrientedGraph, Oriented Graph, mode=cs2
Graph theory objects