vignette|Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale.
En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.
Contrairement au problème de plus court chemin, qui peut être résolu en temps polynomial dans les graphes sans cycle de poids négatif, le problème de la plus longue chaîne est NP-complet; il ne peut donc être résolu en temps polynomial, sauf si P=NP. Des résultats complémentaires montrent que, de plus, ce problème est également difficile à résoudre de manière approchée. En revanche, il a une complexité linéaire pour les graphes orientés acycliques, et il a alors des applications importantes, par exemple dans la détermination du chemin critique dans des problèmes d'ordonnancement, comme ils sont modélisés dans la méthode PERT par exemple.
Pour voir que le problème de la plus longue chaîne est NP-difficile, même dans des graphes non pondérés, on utilise une réduction au problème de la chaîne hamiltonienne : un graphe G possède une chaîne hamiltonienne si et seulement si la plus longue chaîne élémentaire dans G est de longueur n-1, où n est le nombre de sommets de G. Comme on sait que le problème de la chaîne hamiltonienne est NP-complet, cette réduction montre que le problème de la plus longue chaîne, vu comme problème de décision, est aussi NP-complet. Dans ce problème de décision, la donnée est formée d'un graphe G et d'un entier k; le résultat est « oui » si G possède une chaîne de longueur k ou plus, et « non » dans le cas contraire.
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.
En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D.
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.
This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex
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
In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing prob