circuit d'un graphe

Imaginez des rues à sens unique entre quatre carrefours A, B, C et D. En partant de A, les flèches autorisent le trajet A vers B, puis B vers C, puis C vers A. Le retour au point de départ en respectant chaque flèche forme un circuit.

On compte trois arcs parcourus : ce circuit est donc de longueur 3. Un simple dessin en boucle ne suffit pas ; les directions doivent permettre de fermer réellement le trajet.

Dans un graphe orienté, chaque arc possède une origine et une extrémité. Un circuit est une suite finie d'arcs dans laquelle l'extrémité de chaque arc est l'origine du suivant, et dont le sommet final est aussi le sommet initial. Si les sommets rencontrés sont notés v₀, v₁, jusqu'à v_k, la condition de fermeture s'écrit $v_k=v_{0}v\_k=v\_0$. La longueur du circuit est le nombre k d'arcs parcourus, et non le nombre de sommets affichés dans la suite fermée.

Le cas k = 1 est possible lorsqu'un arc part d'un sommet et revient immédiatement sur ce même sommet : cet arc est une boucle. Dans un graphe non orienté, la notion correspondante est celle de cycle, composé d'arêtes sans direction. L'expression « cycle orienté » est aussi employée pour un circuit. Les conventions sur la répétition éventuelle de sommets ou d'arcs varient selon les ouvrages ; il faut donc vérifier si le mot « circuit » y impose en plus une condition de simplicité.

Un circuit repose sur quatre données liées. Le graphe orienté fournit les sommets et les arcs munis d'un sens. La suite ordonnée indique quels arcs sont parcourus. La continuité impose que deux arcs successifs se raccordent au même sommet. Enfin, la fermeture impose que l'arrivée du dernier arc soit le départ du premier. Sans raccordement, on n'a pas un chemin ; sans fermeture, on a seulement un chemin orienté.

Dans le graphe conducteur, les arcs A→B, B→C et C→A satisfont ces deux contraintes. L'arc C→D appartient au graphe, mais pas au circuit choisi. La position des lettres, la forme des flèches ou la longueur dessinée des arcs ne définissent pas le circuit : seuls les sommets, les arcs, leur ordre et leur orientation comptent. Ces données suffisent à vérifier la fermeture et à calculer la longueur.

On considère les sommets A, B, C et D, ainsi que les arcs A→B, B→C, C→A et C→D. On teste la suite A→B→C→A.

1. L'arc A→B existe : le parcours peut partir de A.
2. L'arc B→C existe et reprend au sommet B, où le premier arc arrive.
3. L'arc C→A existe et reprend au sommet C.
4. Le dernier arc arrive en A, qui est aussi le sommet de départ : la suite est fermée.
5. La suite contient trois arcs, donc sa longueur vaut 3.

Le contrôle consiste à suivre les pointes de flèche sans interruption, puis à recompter A→B, B→C et C→A. En revanche, A→B→C→D n'est pas un circuit : les trois arcs s'enchaînent, mais l'arrivée D diffère du départ A.

Dans un planning de tâches, un arc peut signifier qu'une tâche dépend d'une autre. Si le suivi des flèches ramène à la tâche initiale, les dépendances sont circulaires. Un tri topologique convient seulement en l'absence de circuit.

Dans un réseau de circulation ou de flot, un circuit repère un parcours orienté qui revient à son origine. Lorsque le trajet ne revient pas au départ, on le traite comme un chemin plutôt que comme un circuit.

Pour examiner un graphe, on suit les arcs dans leur sens en mémorisant les sommets rencontrés. Le retour à un sommet déjà engagé dans le parcours signale une fermeture possible ; il reste alors à isoler la suite d'arcs concernée.

Chemin orienté. Ses arcs s'enchaînent dans le bon sens, mais son arrivée peut différer de son départ. Ainsi, A→B→C→D est un chemin et non un circuit.

Cycle d'un graphe non orienté. Il se parcourt le long d'arêtes qui n'ont pas de sens imposé. Un circuit exige au contraire que chaque arc soit suivi selon son orientation ; la même forme dessinée peut donc donner un verdict différent.

Longueur 1. Une boucle est déjà un circuit : l'unique arc part d'un sommet et y revient. Exiger au moins trois arcs ferait manquer ce cas charnière explicitement admis ici.

Orientation trompeuse. Une forme polygonale fermée ne prouve rien si une flèche pointe dans le mauvais sens. Il faut contrôler les arcs successivement, et non se fier au contour visible.

Vocabulaire variable. Certains textes réservent « circuit » à une marche fermée sans répétition d'arcs, ou emploient « cycle orienté » avec une condition supplémentaire sur les sommets. Avant un raisonnement, il faut reprendre la convention donnée et préciser les répétitions autorisées.

Graphe non connexe. Un circuit peut exister dans une composante sans concerner les autres. L'absence de circuit autour d'un sommet isolé ne permet donc pas de conclure pour tout le graphe.

Le graphe orienté et non-orienté précise ce que le sens des liaisons change dans un parcours. La fiche Boucle approfondit le circuit réduit à un seul arc.

À un niveau plus avancé, la recherche de circuits conduit à étudier les composantes fortement connexes : à l'intérieur d'une telle composante, chaque sommet est accessible depuis chaque autre par un chemin orienté. Cette structure aide à localiser les zones où un retour est possible.