Avant Hamilton : L’héritage d’Euler – 1736

Tout est parti d’une ligne de code. En travaillant sur mes développements d’applications, notamment sur juniper.php, l’envie m’est venue de vous parler des graphes hamiltoniens. Ces structures fascinantes qui tentent de relier chaque point d’un réseau sans jamais repasser par le même chemin ne sont pas connues de tout le monde. (hein Pierre L ?)

Mais avant d’évoquer ces graphes, retournons en 1736 et parlons des graphes Eulériens :

🌉 L’énigme des Sept Ponts

À l’époque, les habitants de Königsberg se posaient un défi qui semblait être un simple jeu de l’esprit : Peut-on se promener en ville en traversant chacun des sept ponts une seule fois, et revenir à son point de départ ?

Plutôt que de sortir ses chaussures de marche, (Ceux qui lisent vraiment mes publications ont remarqué le lien Amazon douteux – On ne cherche pas à acheter des chaussures de randonnée quand on lit un billet sur les graphes eulériens.) Euler a sorti sa plume. Il a compris que la géographie précise de la ville n’importait pas. Ce qui comptait, c’était la topologie :

• Les quartiers devinrent des sommets (points).
• Les ponts devinrent des arêtes (traits).

🚪 La règle de l’Entrée et de la Sortie

L’illumination d’Euler tient en une observation toute bête : si vous n’habitez pas dans un quartier, pour chaque pont par lequel vous entrez (Intérieur), vous devez impérativement ressortir par un autre pont (Extérieur).

C’est une question de transit (à la mode 😊) :

• Chaque passage « consomme » deux ponts.
• Conséquence directe : pour qu’un parcours soit possible sans rester coincé comme un rat dans un quartier, chaque sommet doit être relié à un nombre pair de ponts.

Le cas de Königsberg : Euler regarde la carte. L’île centrale a 5 ponts. Les autres quartiers en ont 3.

• 3 ponts ? Vous entrez, vous sortez… et si vous revenez, vous êtes coincé à l’intérieur (ou vous ne pouvez plus y entrer si vous en étiez parti).
• 5 ponts ? Même problème après deux passages.

Puisque tous les quartiers de Königsberg avaient un nombre impair de ponts, Euler a pu affirmer, sans même enfiler ses chaussures de randonnée, que la balade était une impasse mathématique.

🚶 Chemin ou Cycle : Une nuance de taille

Pour bien comprendre Euler, il faut distinguer deux types de prouesses : le chemin et le cycle.

• Le Chemin Eulérien : C’est la version « aller simple ». Vous partez d’un point A, vous traversez chaque pont une fois, et vous terminez votre balade à un point B. Pour réussir cela, Euler a démontré qu’il fallait au maximum deux sommets impairs (votre point de départ et votre point d’arrivée). C’est le cas d’e votre ‘un pont unique entre deux îlots : vous partez de l’un (impair), vous arrivez sur l’autre (impair), et tout le monde est content.
• Le Cycle Eulérien : C’est la version « boucle parfaite ». Vous voulez traverser chaque pont une fois, mais avec l’obligation de revenir boire un café à votre point de départ. Ici, la règle est impitoyable : il ne doit y avoir aucun sommet impair. Pourquoi ? Parce que chaque quartier doit pouvoir être « traversé » (une entrée = une sortie). Si vous partez d’un sommet, vous utilisez une sortie ; il vous faudra impérativement une entrée pour y revenir à la fin.

Le verdict pour Königsberg : Les habitants ne cherchaient pas seulement à traverser les ponts, ils voulaient faire une boucle. Avec quatre sommets impairs, la ville échouait sur les deux tableaux : ni chemin possible pour traverser, ni cycle pour revenir.

🧮 Conclusion : Le Théorème d’Euler (1736)

Pour clore ce chapitre historique, sortons des rues de Kaliningrad pour poser la loi mathématique qui régit, encore aujourd’hui, nos réseaux de données. Soit un graphe connexe G = (V, E), où V est l’ensemble des sommets et E l’ensemble des arêtes.

Le verdict d’Euler, qui marque la naissance de la topologie, peut se résumer ainsi :

1. Condition de Cycle Eulérien

Un graphe G admet un cycle passant par chaque arête de E exactement une fois si, et seulement si, chaque sommet de V a un degré pair :

\forall v \in V, \deg(v) \equiv 0 \pmod{2}

2. Condition de Chemin Eulérien

Un graphe G admet un chemin passant par chaque arête deE exactement une fois si, et seulement si, le nombre de sommets de degré impair est exactement 0 ou 2 :

\text{card}({v \in V \mid \deg(v) \equiv 1 \pmod{2}}) \in \left\{0; 2\right\}

C’est ici que réside toute la puissance de la découverte d’Euler : il a transformé un problème de parcours spatial en une simple propriété de comptage algébrique.

En termes d’algorithmique (ce qui nous intéresse pour des outils comme juniper.php), la complexité pour vérifier si un graphe est eulérien est de classe O(|E|).

💻 Pourquoi Euler est le meilleur ami du développeur

Dans le cadre du développement d’applications comme juniper.php, la performance est reine. Le problème d’Euler est ce qu’on appelle un problème linéaire.

Qu’est-ce que cela signifie concrètement ?

La complexité est notée O(|E|), où |E| est le nombre d’arêtes (les ponts ou les connexions de votre réseau).

Pour vérifier si un réseau est « Eulérien », l’algorithme procède de manière très simple :

1. Parcours unique : L’ordinateur « lit » la liste des arêtes une seule fois.
2. Incrémentation : Pour chaque arête reliant deux points A et B, il ajoute 1 au compteur de A et 1 au compteur de B.
3. Vérification : À la fin, il regarde si les compteurs sont tous pairs (pour un cycle) ou s’il n’y a que deux impairs (pour un chemin).

Le résultat : Si votre réseau contient 1 000 000 de câbles, l’ordinateur fera environ 1 000 000 d’opérations. C’est quasi instantané pour un processeur moderne. On dit que le problème est P (Polynomial), ou plus simplement : « facile ».

🚴‍♂️ L’exemple du facteur : quand compter suffit

Imaginons maintenant un facteur qui doit distribuer le courrier entre deux petits villages.

Premier cas : le village carré.

Quatre maisons, reliées par quatre routes formant un carré parfait. Chaque maison possède exactement deux routes. Le facteur peut partir de n’importe où, passer une seule fois sur chaque route, et revenir à son point de départ sans réfléchir. Les degrés sont pairs, le cycle est garanti. Euler sourit.

Deuxième cas : le même village… avec une diagonale en plus.
On ajoute une route directe entre deux maisons opposées. Cette fois, deux maisons ont trois routes. Le facteur commence sa tournée, traverse la diagonale… et se retrouve tôt ou tard bloqué. Une route reste inutilisée, ou bien il lui faudrait repasser par un chemin déjà emprunté.
Rien n’a changé visuellement de manière spectaculaire. Pourtant, mathématiquement, tout s’est effondré.

La beauté du raisonnement d’Leonhard Euler est là :
il n’a pas besoin de simuler la tournée du facteur, ni de tester des parcours. Il se contente de compter. Deux sommets impairs suffisent à ruiner l’idée d’un cycle. Un simple ajout d’arête peut faire basculer tout le problème.

Et c’est précisément ce caractère local, comptable et immédiat qui rend les graphes eulériens si dociles pour un ordinateur.

Exemple Python

# Graphe non orienté : sommet -> voisins
def est_eulerien(g):
    # on compte le degré de chaque sommet
    degres = [len(v) for v in g.values()]
    # cycle eulérien ⇔ tous les degrés sont pairs
    return all(d % 2 == 0 for d in degres)

# Carré : OK
carre = {
    "A": ["B","D"], "B": ["A","C"],
    "C": ["B","D"], "D": ["C","A"]
}

# Carré + diagonale : KO
diagonale = {
    "A": ["B","D","C"], "B": ["A","C"],
    "C": ["B","D","A"], "D": ["C","A"]
}

print(est_eulerien(carre))       # True
print(est_eulerien(diagonale))   # False

Copier coller ce code dans le bac à sable Python

🧠 Compter, toujours compter… mais autrement

La force du raisonnement d’Euler dans les graphes eulériens ne réside pas dans l’exploration de tous les chemins possibles, mais dans une idée beaucoup plus élégante : remplacer un parcours complexe par un simple comptage.

En observant uniquement le nombre d’arêtes incidentes à chaque sommet, il devient possible de trancher instantanément une question qui semblait, à première vue, relever de l’expérimentation ou de l’essai-erreur.

Cette approche par le comptage se retrouve dans de nombreux problèmes de mathématiques discrètes. Par exemple, lorsqu’il s’agit de dénombrer les triangles dans une figure géométrique, une inspection visuelle atteint rapidement ses limites.

En revanche, une modélisation combinatoire permet d’énumérer systématiquement toutes les configurations possibles de trois points formant un triangle. Cette idée est mise en œuvre dans l’outil interactif suivant :

site2wouf.fr : Dénombrer des triangles

Dans le même esprit, le dénombrement algorithmique repose souvent sur la génération contrôlée de combinaisons.

itertools.combinations

Le module Python itertools.combinations illustre parfaitement cette philosophie : il permet d’explorer toutes les sélections possibles sans doublons ni permutations inutiles, avec un code à la fois lisible et efficace.

Cette approche est détaillée dans l’article suivant, qui montre comment la combinatoire classique trouve naturellement sa place dans la programmation moderne :

Des Mathématiques combinatoires avec Python et itertools.combinations

Ainsi, des ponts de Königsberg aux triangles cachés dans une figure, une même idée traverse les siècles : avant de chercher les chemins, il faut apprendre à compter.

Le contraste brutal avec Hamilton

Si vous changez la question pour chercher un chemin Hamiltonien (visiter chaque sommet comme pour juniper.php), l’algorithme ne peut plus se contenter de compter les degrés.

On bascule dans le monde des problèmes NP-complets. Pour un réseau de même taille, l’ordinateur pourrait devoir tester des milliards de combinaisons, une tâche qui prendrait des siècles plutôt que des millisecondes…

On a vraiment le temps d’enfiler enfiler ses chaussures de randonnée…

⏳ En cuisine : Le plat « Hamilton » est en mijotage…

Si Euler nous a offert une recette simple, élégante et rapide à exécuter pour nos processeurs, le chef Hamilton, lui, nous propose un menu d’une tout autre complexité.

Mais passer des arêtes aux sommets, c’est un peu comme passer d’une addition à une équation à mille inconnues.

En coulisses, je peaufine actuellement la suite de cette exploration. Nous verrons comment un problème en apparence identique fait basculer l’informatique dans le monde des problèmes NP-complets, là où même les serveurs les plus puissants commencent à transpirer.

D’ici là, n’hésitez pas à tester vos propres graphes sur site2wouf.fr/juniper.php. Vérifiez vos degrés, comptez vos impairs, et préparez vos neurones : la suite arrive très vite, et elle ne sera pas aussi clémente que ce bon vieux Leonhard !