graphe eulérien

Imaginez un dessin formé de points reliés par des traits. Le défi consiste à suivre chaque trait une seule fois, sans lever le crayon, puis à revenir au point de départ. Si ce parcours est possible, le dessin représente un graphe eulérien.

Un contrôle simple suffit lorsque le graphe est d'un seul tenant : chaque point doit recevoir un nombre pair de traits. Deux traits permettent d'y entrer puis d'en sortir ; quatre traits autorisent deux passages, et ainsi de suite.

Un graphe non orienté est eulérien lorsqu'il possède un cycle eulérien : une suite fermée d'arêtes qui utilise chacune des arêtes exactement une fois. Les sommets peuvent être rencontrés plusieurs fois. Le sommet choisi au départ est aussi celui de l'arrivée.

Pour un graphe connexe, le théorème d'Euler donne un critère nécessaire et suffisant : le graphe est eulérien si et seulement si chaque sommet a un degré pair. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Cette parité traduit l'équilibre des passages : toute arrivée le long d'une arête doit pouvoir être suivie d'un départ le long d'une autre.

Un chemin eulérien utilise également chaque arête exactement une fois, mais il n'est pas nécessairement fermé. Dans un graphe connexe, un tel chemin ouvert existe lorsque deux sommets exactement ont un degré impair. Il part de l'un de ces sommets et finit à l'autre. Avec zéro sommet impair, le parcours peut être fermé ; avec plus de deux sommets impairs, aucun parcours eulérien n'existe.

Le graphe conducteur comporte quatre sommets A, B, C et D, reliés par les arêtes AB, BC, CD et DA. Les sommets sont les points de jonction ; les arêtes sont les liaisons à parcourir. L'incidence indique quelles arêtes touchent chaque sommet, et le degré compte ces arêtes. Ici, chaque sommet est incident à deux arêtes. La connexité garantit qu'une chaîne de liaisons permet de passer entre deux sommets quelconques. Le cycle A–B–C–D–A ordonne enfin les quatre arêtes sans en répéter aucune.

La position des points, la longueur des traits et la forme carrée du dessin ne définissent pas le graphe. Seules comptent les jonctions et leurs liaisons. Ces données suffisent à calculer les degrés, à vérifier la connexité et à chercher un cycle eulérien.

Considérons quatre sommets A, B, C et D et quatre arêtes AB, BC, CD et DA. Le graphe est connexe : les quatre sommets appartiennent à une même chaîne de liaisons.

1. Comptons les arêtes incidentes : A touche AB et DA ; B touche AB et BC ; C touche BC et CD ; D touche CD et DA.
2. Chaque sommet a donc le degré 2, qui est pair.
3. Le critère d'Euler s'applique puisque le graphe est connexe : il est eulérien.
4. Partons de A et suivons AB, puis BC, puis CD, puis DA. Le parcours A–B–C–D–A revient à A après avoir utilisé les quatre arêtes une seule fois.

Le contrôle se refait dans l'autre sens : A–D–C–B–A parcourt encore exactement AB, BC, CD et DA. Le sens du parcours change, pas son caractère eulérien.

Dans un problème de dessin d'un seul trait, on traduit les jonctions en sommets et les traits en arêtes. On compte ensuite les degrés avant d'essayer des parcours au hasard. Si tous sont pairs et que le dessin est connexe, on cherche un cycle qui revient au départ.

Pour contrôler un itinéraire qui doit emprunter chaque liaison une fois, on vérifie d'abord ses extrémités. Deux sommets impairs imposent un chemin ouvert entre eux ; zéro sommet impair autorise un parcours fermé. Avec plus de deux sommets impairs, il faut modifier les liaisons ou renoncer à la contrainte d'un passage unique.

Dans le carré A–B–C–D–A, supprimer l'arête DA rend A et D impairs. Le bon objectif n'est alors plus un cycle, mais le chemin ouvert A–B–C–D.

Un cycle eulérien doit utiliser chaque arête exactement une fois ; il peut repasser par un sommet. Un cycle hamiltonien doit au contraire visiter chaque sommet exactement une fois, sans exiger l'emploi de toutes les arêtes. Le critère décisif est donc l'objet compté : les arêtes pour Euler, les sommets pour Hamilton.

Dans le carré A–B–C–D–A, le même parcours possède les deux propriétés. L'ajout d'une diagonale AC suffit toutefois à les séparer : le tour du carré visite encore chaque sommet une fois, mais il laisse la diagonale inutilisée et n'est donc pas eulérien.

La parité ne suffit pas sans connexité. Deux cycles séparés ont uniquement des sommets de degré 2, mais aucun parcours continu ne peut couvrir leurs arêtes à tous les deux. Il faut donc vérifier que toutes les arêtes appartiennent à une même composante avant d'appliquer le critère.

Deux sommets impairs ne rendent pas le graphe eulérien au sens retenu ici : ils donnent seulement un chemin eulérien ouvert. Dans le carré privé de DA, A et D ont le degré 1 ; le parcours commence à l'un et finit à l'autre, sans retour possible au départ.

Le tracé visuel peut tromper. Deux arêtes qui se croisent dans la représentation ne créent un sommet que si leur intersection est déclarée comme une jonction. Avant de compter les degrés, il faut donc identifier les véritables sommets plutôt que toutes les intersections apparentes.

La fiche degré d'un sommet d'un graphe approfondit le comptage local dont la parité décide de l'existence d'un cycle eulérien.

La fiche graphe connexe précise la condition globale qui empêche un parcours d'être bloqué dans une composante séparée.