graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

. A polytree 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 Carolin ...

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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

. Therefore, the same sequence of numbers also solves the

graph enumeration In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the g ...

problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.

Constrained orientations

strong orientation In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the design of one-way road networks. ...

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

. 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 A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...

. An

acyclic orientation In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...

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 In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly c ...

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 ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in South ...

with at most colors. Acyclic orientations and totally cyclic orientations are related to each other by

planar dual In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

ity. An acyclic orientation with a single source and a single sink is called a

bipolar orientation In graph theory, a bipolar orientation or ''st''-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes the graph to become a directed acyclic graph with a single source ''s'' and a single sink ' ...

. A

transitive orientation Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case, a grammatical case to mark ar ...

is an orientation such that the resulting directed graph is its own

transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...

. The graphs with transitive orientations are called comparability graphs; they may be defined from a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

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 In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the ...

. 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 graph In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lat ...

s 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 models. A

Pfaffian orientation In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientati ...

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 graphs, but not for certain other graphs. They are used in the

FKT algorithm The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, c ...

for counting perfect matchings.

References

External links

* *{{mathworld, OrientedGraph, Oriented Graph, mode=cs2 Graph theory objects

Oriented graphs

Constrained orientations

See also

References

External links