graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, an orientation of an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

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 and may be arrows of the graph). A

tournament A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...

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

. A polytree is an orientation of an undirected

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

. Sumner's conjecture 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, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

. 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 graph, undirected or directed graphs of certain types, typically as a function of the number of v ...

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 (graph theory), orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the des ...

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 is totally cyclic if and only if it is a strong orientation of every connected component of .

Robbins' theorem In graph theory, Robbins' theorem, named after , states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph , turning it into ...

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 railway) without blocking the path underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somet ...

. An acyclic orientation is an orientation that results in a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...

. 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 ''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. Dictionary definitions The word ''colored'' wa ...

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 In mathematics, the transitive closure of a homogeneous binary relation on a set (mathematics), set is the smallest Relation (mathematics), relation on that contains and is Transitive relation, transitive. For finite sets, "smallest" can be ...

. The graphs with transitive orientations are called

comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...

s; they may be defined from a

partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

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

. 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 (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...

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. Sometimes called statistical physics or statistical thermodynamics, its applicati ...

in the theory of ice-type models. 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 (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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