Recherche de cycles.

La recherche de cycles (ou circuits dans le cas orienté) est un problème récurrent en algorithmique des graphes, avec différentes variantes suivant les propriétés recherchées sur ces cycles (par exemple des propriétés de longueur). Les applications sont très nombreuses, allant des problèmes de "postiers" ou "voyageurs de commerce" à l'étude de réseaux de gènes.

L'objectif de ce sujet est de présenter une synthèse sur la complexité de ces recherches. On se concentrera sur la recherche de cycles (ou circuits) qui sont des sous-graphes du graphe initial (on pourrait imaginer encore d'autres variantes en les recherchant comme mineurs du graphe initial).
Un singleton ne sera pas considéré comme un cycle ou circuit.

Pour vous guider, vous pouvez essayer de remplir autant de cases que possibles du tableau ci-dessous (pas forcément tout :-)), en donnant une borne sur la complexité de chacune des variantes proposées. Les lignes décrivent différents critères de recherche de cycles (ou circuits), principalement basés sur la longueur (c'est à dire le nombre d'arêtes ou d'arcs). Les colonnes énumèrent les variantes obtenues en se plaçant dans le cas non orienté (cycles) ou orienté (circuits), et en fonction des différents types de cycles (ou circuits) :


Graphes non orientés
Graphes orientés

cycle standard
cycle élémentaire
cycle sans corde
circuit standard
circuit élémentaire
circuit sans corde
Existence (sans autre critère)






Longueur maximum






Longueur minimum






Longueur = k, pour un k fixé






Longueur impaire






Longueur paire







Cela fait bien sûr beaucoup de variantes possibles. Certaines correspondent à des problèmes classiques, d'autres moins. Vous pouvez ne donner que le principe général des algorithmes, voire juste une référence, pour certaines variantes dont vous avez la complexité, mais détaillez un algorithme et son analyse pour au moins l'un des problèmes.

Quelques références (pas exhaustif).

Retour à la page des sujets.