Chemins, circuits et chemin hamiltonien

Un chemin est une suite de sommets dans laquelle chaque sommet est relié au suivant par un arc ; sa longueur est son nombre d'arcs. Un circuit est un chemin qui revient à son point de départ, et un chemin hamiltonien est un chemin qui passe une fois et une seule par chaque sommet du graphe. Ces trois notions servent à tout le reste du cours : on compte les chemins avec les matrices, on cherche les plus courts, on vérifie qu'un graphe de tâches n'a pas de circuit. Ce chapitre les définit et donne une méthode pour trouver un chemin hamiltonien, une question posée au sujet de l'E3 2026.

Chemin et longueur d'un chemin

Un chemin de longueur p est une suite de p + 1 sommets (x₀, x₁, …, xₚ) telle que chaque couple (x₀, x₁), (x₁, x₂), …, (xₚ₋₁, xₚ) soit un arc du graphe. x₀ est l'origine du chemin, xₚ son extrémité. On l'écrit (x₀, x₁, …, xₚ) ou x₀ → x₁ → … → xₚ.

Sur le graphe G du ticket (arcs A → B, A → E, B → A, B → C, C → C, C → D, D → C, D → E), voici quelques chemins :

Un chemin peut repasser par un sommet, comme (A, B, A, E), et emprunter une boucle, comme (C, C, D). Pour vérifier qu'une suite de sommets est un chemin, contrôle chaque arc un par un dans le tableau des successeurs ou la matrice : (A, C, D) n'est pas un chemin de G, car (A, C) n'est pas un arc.

Un chemin qui ne passe pas deux fois par le même sommet est dit élémentaire : (B, C, D, E) l'est, (A, B, A, E) ne l'est pas. Dans un graphe à n sommets, un chemin élémentaire a au plus n − 1 arcs.

Circuit et boucle

Un circuit est un chemin de longueur au moins 1 dont l'extrémité est égale à l'origine. Une boucle est un circuit de longueur 1.

Dans G :

• (C, C) est une boucle, un circuit de longueur 1 ;
• (A, B, A) et (C, D, C) sont des circuits de longueur 2 ;
• (C, D, C, C) est un circuit de longueur 3 qui emprunte la boucle.

On ne distingue pas un circuit selon son point de départ : (A, B, A) et (B, A, B) décrivent le même circuit.

Un graphe sans circuit ne permet jamais de revenir sur ses pas. C'est le cas d'un graphe de dépendances (un logiciel ne peut pas dépendre, même indirectement, de lui-même) et du graphe des tâches d'un projet (une tâche ne peut pas attendre sa propre fin). Les graphes sans circuit ont des propriétés précieuses : on peut ranger leurs sommets par niveaux (chapitre 5) et y chercher un plus long chemin, qui donne la durée d'un projet (chapitre 8).

Chemin hamiltonien et circuit hamiltonien

Un chemin hamiltonien est un chemin qui passe une fois et une seule par chaque sommet du graphe. Dans un graphe à n sommets, il a donc exactement n sommets et n − 1 arcs. Un circuit hamiltonien est un circuit qui passe une fois et une seule par chaque sommet avant de revenir à son départ ; il a n arcs.

Le nom vient du mathématicien irlandais William Rowan Hamilton, qui inventa vers 1857 un jeu consistant à faire le tour des sommets d'un dodécaèdre sans repasser deux fois au même endroit.

Dans le graphe G du ticket, le chemin (A, B, C, D, E) passe par les cinq sommets, chacun une fois, en empruntant les arcs A → B, B → C, C → D et D → E, qui existent tous : c'est un chemin hamiltonien, de longueur 4. Il raconte le parcours « normal » d'un ticket : nouveau, attribué, en cours, résolu, clos, sans retour en arrière.

G n'a pas de circuit hamiltonien : E est un puits, aucun arc n'en repart, donc aucun circuit ne peut passer par E.

Méthode pour trouver un chemin hamiltonien

Il n'existe pas de méthode rapide qui marche pour tous les graphes : décider si un grand graphe a un chemin hamiltonien est un problème réputé difficile en informatique. Mais sur les petits graphes de l'E3, quatre réflexes suffisent.

1. Repère les sources et les puits. Une source (aucun prédécesseur) ne peut être que le premier sommet d'un chemin hamiltonien, un puits (aucun successeur) que le dernier. S'il y a deux sources ou deux puits, il n'y a pas de chemin hamiltonien.
2. Pars de la source s'il y en a une, sinon d'un sommet qui a peu de prédécesseurs.
3. Avance de successeur en successeur avec le tableau des successeurs, en choisissant à chaque étape un sommet pas encore visité. Commence par les sommets qui ont peu d'options.
4. Si tu es bloqué avant d'avoir tout visité, reviens au dernier choix et essaie un autre successeur.

Pour justifier ta réponse, il suffit de vérifier deux choses : chaque sommet apparaît une fois et une seule, et chaque arc du chemin existe. Pour justifier qu'il n'y en a pas, l'argument des sources et des puits est le plus rapide ; sinon, il faut montrer que tous les essais échouent.

Exemple : un graphe sans chemin hamiltonien. Le graphe de sommets A, B, C, D, E et d'arcs (A, C), (B, C), (C, D), (C, E), (D, E) a deux sources, A et B : un chemin hamiltonien devrait commencer à la fois par A et par B. Il n'en a donc pas.

Interpréter un chemin hamiltonien

Les sujets demandent souvent ce que signifie un chemin hamiltonien dans le contexte. La réponse suit toujours le même modèle : « on passe par tous les [sommets du contexte], chacun une seule fois, dans l'ordre [du chemin] ».

• Au sujet de l'E3 2026, les sommets étaient les zones d'un restaurant (accueil, buffets, caisse) : un chemin hamiltonien de l'accueil à la caisse est un parcours qui passe une fois par chaque zone, sans revenir se servir (corrigé proposé sur le blog).
• Dans le graphe des écrans d'une application, un chemin hamiltonien est un scénario de test qui visite chaque écran une fois.
• Dans un graphe de sites reliés par des trajets possibles, un circuit hamiltonien est une tournée de maintenance qui passe une fois sur chaque site et revient au point de départ. Chercher la tournée la plus courte est le célèbre problème du voyageur de commerce, hors programme.

Exercices

Exercice 1 sur 5 Chemins dans le graphe du ticket Réussi À revoir

On reprend le graphe G (arcs A → B, A → E, B → A, B → C, C → C, C → D, D → C, D → E).

1. (B, A, E) et (B, C, E) sont-ils des chemins ? Donne leur longueur s'il y a lieu.
2. Donne tous les chemins de longueur 3 de B vers E.
3. Donne deux chemins de longueur 5 de A vers E.
4. Donne un circuit de longueur 4 passant par C.

Voir la réponseMasquer la réponse de l'exercice 1

1. (B, A, E) : les arcs (B, A) et (A, E) existent, c'est un chemin de longueur 2. (B, C, E) : l'arc (C, E) n'existe pas, ce n'est pas un chemin.
2. On cherche (B, x, y, E). Les prédécesseurs de E sont A et D, donc y = A ou y = D. Si y = A, x devrait être à la fois successeur de B et prédécesseur de A ; or le seul prédécesseur de A est B, et (B, B) n'est pas un arc : impossible. Si y = D, il faut x successeur de B et prédécesseur de D : x = C convient. Il y a un seul chemin de longueur 3 de B vers E : (B, C, D, E).
3. Par exemple (A, B, C, C, D, E), qui emprunte la boucle, et (A, B, A, B, A, E), qui fait deux fois l'aller-retour entre A et B. Ce sont les deux seuls.
4. Par exemple (C, D, C, D, C), qui fait deux fois l'aller-retour entre C et D, ou (C, C, D, C, C), qui combine le circuit (C, D, C) et deux passages par la boucle.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 Chemins hamiltoniens Réussi À revoir

On reprend le graphe K du chapitre 1 : arcs (A, B), (A, D), (B, C), (C, A), (C, D), (D, D).

1. Trouve tous les chemins hamiltoniens de K.
2. K a-t-il un circuit hamiltonien ?

Voir la réponseMasquer la réponse de l'exercice 2

1. D n'a pas d'autre successeur que lui-même : un chemin hamiltonien, qui ne passe qu'une fois par D, doit finir en D. On cherche donc un ordre de A, B, C suivi de D. En partant de A : A → B → C → D convient. En partant de B : B → C → A → D convient. En partant de C : C → A → B, puis B → D n'existe pas ; C → A → D laisse B de côté. Il y a deux chemins hamiltoniens : (A, B, C, D) et (B, C, A, D).
2. Un circuit hamiltonien devrait repartir de D vers un autre sommet. Le seul arc qui part de D est la boucle : pas de circuit hamiltonien.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 La tournée de maintenance Réussi À revoir

Un technicien doit passer sur cinq sites A, B, C, D, E. Les trajets possibles, à cause des horaires de livraison et des sens uniques, sont : A → B, A → C, B → C, C → D, C → E, D → B, D → E, E → A.

1. Écris la matrice d'adjacence de ce graphe.
2. Trouve un circuit hamiltonien et interprète-le.
3. Le chemin (A, C, D, B) est-il un circuit ? Est-il hamiltonien ?

Voir la réponseMasquer la réponse de l'exercice 3

1. La matrice, sommets dans l'ordre alphabétique :

	A	B	C	D	E
A	0	1	1	0	0
B	0	0	1	0	0
C	0	0	0	1	1
D	0	1	0	0	1
E	1	0	0	0	0

2. Le seul arc qui arrive en A part de E, et le seul qui part de B va en C. On essaie A → B → C → D → E → A : tous les arcs existent. (A, B, C, D, E, A) est un circuit hamiltonien : le technicien peut visiter les cinq sites, chacun une fois, et revenir à son point de départ. C'est d'ailleurs le seul.
3. Le chemin (A, C, D, B) existe (arcs A → C, C → D, D → B), mais il finit en B, pas en A : ce n'est pas un circuit. Il ne passe pas par E : il n'est pas hamiltonien non plus.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 Sources, puits et chemin hamiltonien Réussi À revoir

Pour chaque graphe, dis s'il a un chemin hamiltonien, en justifiant.

1. Sommets A, B, C, D ; arcs (A, B), (A, C), (B, D), (C, D).
2. Sommets A, B, C, D ; arcs (A, B), (B, C), (C, D), (A, C), (B, D).
3. Sommets A, B, C, D, E ; arcs (A, B), (B, C), (C, A), (C, D), (E, D).

Voir la réponseMasquer la réponse de l'exercice 4

1. A est la seule source, D le seul puits. Après A, il faudrait passer par B et C avant D, mais il n'y a d'arc ni de B vers C ni de C vers B. Pas de chemin hamiltonien.
2. (A, B, C, D) : les arcs A → B, B → C, C → D existent. C'est un chemin hamiltonien.
3. E n'a pas de prédécesseur et D n'a pas de successeur : un chemin hamiltonien commencerait par E et finirait par D. Mais le seul successeur de E est D : on arrive en D tout de suite, sans pouvoir visiter A, B, C. Pas de chemin hamiltonien.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Vrai ou faux Réussi À revoir

Justifie chaque réponse.

1. Un chemin hamiltonien d'un graphe à 6 sommets a pour longueur 6.
2. Une boucle est un circuit.
3. Si un graphe a un circuit hamiltonien, il a un chemin hamiltonien.
4. Un graphe qui a deux puits n'a pas de chemin hamiltonien.

Voir la réponseMasquer la réponse de l'exercice 5

1. Faux : il passe par 6 sommets, donc emprunte 5 arcs ; sa longueur est 5.
2. Vrai : c'est un circuit de longueur 1.
3. Vrai : en retirant le dernier arc d'un circuit hamiltonien (celui qui revient au départ), on obtient un chemin qui passe une fois par chaque sommet.
4. Vrai : un puits ne peut être que le dernier sommet d'un chemin hamiltonien, et il ne peut pas y avoir deux derniers sommets.

Tu avais trouvé ?

Oui, j'avais bonPas encore