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 orientation. The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings. The planar dual 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 by making two orientations adjacent when they differ in the direction of a single edge. Orientations of trees are always acyclic, and give rise to polytrees. Acyclic orientations of complete graphs are called transitive tournaments. The bipolar orientations are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar. 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 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 (shown), there are 24 different vertex sequences, but only 14 possible acyclic orientations. The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has at most k vertices if and only if it can be colored with at most k colors.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (14)

Cours associés (4)

Séances de cours associées (39)

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 t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph. Let G = (V,E) be an undirected graph with n = |V| vertices. An orientation of G is an assignment of a direction to each edge of G, making it into a directed graph.

Polynôme de Tutte

Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe .

Acyclic orientation

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

MATH-506: Topology IV.b - cohomology rings

Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a

Sans titre CS-250: Algorithms I

Inférence causale : Structures de graphes d'apprentissage MGT-416: Causal inference

Explore l'inférence causale à travers des structures de graphes d'apprentissage pour le raisonnement causal à partir de données d'observation.

Réseaux bayésiens : factorisation et échantillonnage MGT-448: Statistical inference and machine learning

Explique les méthodes de factorisation et d'échantillonnage des réseaux bayésiens à l'aide des GAD et de l'élimination des variables.