Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème de la plus longue chaîne
Résumé
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.
Source officielle
À 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.