acyclic orientation
   HOME

TheInfoList



OR:

In
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 acyclic orientation of an
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is an assignment of a direction to each edge (an
orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...
) that does not form any
directed cycle Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
and therefore makes it into 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 v ...
. Every graph has an acyclic orientation. The
chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
of any graph equals one more than the length of the
longest path In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path ma ...
in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the
chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...
, which counts both acyclic orientations and colorings. The
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-loop ...
of an acyclic orientation is a totally cyclic orientation, and vice versa. The family of all acyclic orientations can be given the structure of a
partial cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial c ...
by making two orientations adjacent when they differ in the direction of a single edge. Orientations of
trees 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, including only woody plants with secondary growth, plants that are u ...
are always acyclic, and give rise to polytrees. Acyclic orientations of
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 ...
s are called transitive tournaments. The
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 ' ...
s are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar.


Construction

Every graph has an acyclic orientation. One way to generate an acyclic orientation is to place the vertices into a sequence, and then direct each edge from the earlier of its endpoints in the sequence to the later endpoint. The vertex sequence then becomes a
topological ordering In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For in ...
of the resulting directed acyclic graph (DAG), and every topological ordering of this DAG generates the same orientation. Because every DAG has a topological ordering, every acyclic orientation can be constructed in this way. However, it is possible for different vertex sequences to give rise to the same acyclic orientation, when the resulting DAG has multiple topological orderings. For instance, for a four-vertex
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
(shown), there are 24 different vertex sequences, but only 14 possible acyclic orientations.


Relation to coloring

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 In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path ma ...
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 Sout ...
with at most colors. The number of acyclic orientations may be counted using the
chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...
\chi_G, whose value at a positive integer is the number of -colorings of the graph. Every graph has exactly , \chi_G(-1), different acyclic orientations, so in this sense an acyclic orientation can be interpreted as a coloring with colors.


Duality

For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if G is a planar graph, and orientations of G are transferred to orientations of the
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-loop ...
graph of G by turning each edge 90 degrees clockwise, then a totally cyclic orientation of G corresponds in this way to an acyclic orientation of the dual graph and vice versa. Like the chromatic polynomial, the
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
T_G of a graph G, can be used to count the number of acyclic orientations of G as T_G(2,0). The duality between acyclic and totally cyclic orientations of planar graphs extends in this form to nonplanar graphs as well: the Tutte polynomial of the dual graph of a planar graph is obtained by swapping the arguments of T_G, and the number of totally cyclic orientations of a graph G is T_G(0,2), also obtained by swapping the arguments of the formula for the number of acyclic orientations.


Edge flipping

The set of all acyclic orientations of a given graph may be given the structure of a
partial cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial c ...
, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge. This implies that when two different acyclic orientations of the same graph differ in the directions of edges, it is possible to transform one of the orientations into the other one by a sequence of changes of orientation of a single edge, such that each of the intermediate states of this sequence of transformations is also acyclic.


Special cases

Every orientation of a
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, including only woody plants with secondary growth, plants that are ...
is acyclic. The directed acyclic graph resulting from such an orientation is called a polytree. An acyclic 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 ...
is called a transitive tournament, and is equivalent to a
total ordering In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
of the graph's vertices. In such an orientation there is in particular exactly one source and exactly one sink. More generally, an acyclic orientation of an arbitrary graph that has a unique source and a unique 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 a ...
of a graph is an acyclic orientation that equals 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 infinite ...
. Not every graph has a transitive orientation; the graphs that do are the
comparability graph In graph 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, partially orderable grap ...
s.. Complete graphs are special cases of comparability graphs, and transitive tournaments are special cases of transitive orientations.


References

{{reflist Graph theory objects