ponts de Königsberg

Imaginez quatre morceaux de terre reliés par sept ponts. Vous voulez partir d'un lieu, franchir chaque pont une seule fois et ne jamais emprunter deux fois le même passage.

Le plan précis de la ville importe moins que le nombre de ponts qui arrivent à chaque lieu. À Königsberg, ces nombres sont 3, 3, 3 et 5 : ils sont tous impairs. Chaque passage utilise normalement un pont pour entrer et un autre pour sortir. Avec quatre lieux impairs, aucun choix d'itinéraire ne peut donc satisfaire la règle.

Le problème des ponts de Königsberg demande s'il existe un parcours qui franchit chacun des sept ponts exactement une fois. Pour l'étudier, chaque rive ou île devient un sommet, et chaque pont une arête. Plusieurs ponts peuvent relier les deux mêmes sommets : le modèle est donc un graphe non orienté pouvant avoir des arêtes parallèles. Le degré d'un sommet est le nombre d'extrémités d'arêtes qui y aboutissent.

Dans un graphe dont tous les sommets portant une arête appartiennent à une même composante connexe, un parcours utilisant chaque arête exactement une fois est un parcours eulérien. Il existe si le nombre de sommets de degré impair vaut 0 ou 2. Avec deux sommets impairs, le parcours part de l'un et finit à l'autre. Avec zéro sommet impair, il peut revenir à son point de départ et forme alors un circuit eulérien.

Dans le graphe de Königsberg, les quatre degrés sont 3, 3, 3 et 5. Les quatre sommets sont donc impairs : il n'existe ni parcours eulérien ouvert ni circuit eulérien. Cette conclusion, obtenue par Euler, ne dépend pas de la longueur ou de la forme des ponts, mais seulement de leurs raccordements.

On remplace les quatre lieux par les sommets A, B, C et D. Les sept ponts donnent deux arêtes entre A et C, deux entre B et C, une entre C et D, une entre A et D et une entre B et D.

1. Comptez les arêtes incidentes à A : les deux liaisons vers C et la liaison vers D donnent le degré 3.

2. Le même comptage donne le degré 3 pour B. Pour C, les quatre arêtes vers A ou B et l'arête vers D donnent le degré 5. Enfin, D a le degré 3.

3. Il y a donc quatre sommets de degré impair. Un parcours eulérien n'en autorise que zéro ou deux : le trajet demandé est impossible.

Le contrôle se refait sans chercher d'itinéraire : la somme des degrés vaut 3 + 3 + 5 + 3 = 14, soit deux extrémités pour chacun des sept ponts. Le comptage des arêtes est cohérent.

Pour tester un réseau de passages, dessinez un sommet par lieu et une arête par passage. Comptez ensuite les degrés impairs avant de chercher un trajet : quatre sommets impairs ou davantage suffisent à exclure un parcours sans répétition.

Si tous les degrés sont pairs, cherchez un circuit qui revient au départ. S'il existe exactement deux degrés impairs, commencez par l'un de ces sommets et terminez par l'autre. Cette règle suppose que toutes les arêtes à parcourir soient reliées entre elles dans une même composante.

Lorsque le critère échoue, il faut changer la demande plutôt que multiplier les essais au hasard : autoriser la répétition d'au moins un passage, supprimer un passage ou en ajouter un peut modifier la parité des sommets concernés.

Parcours eulérien et parcours hamiltonien. Le premier utilise chaque arête exactement une fois ; le second visite chaque sommet exactement une fois. Un trajet peut satisfaire l'une de ces conditions sans satisfaire l'autre : il faut regarder si la contrainte porte sur les ponts ou sur les lieux.

Parcours eulérien et circuit eulérien. Un parcours peut avoir des points de départ et d'arrivée distincts lorsque deux sommets sont impairs. Un circuit doit revenir au départ et exige que tous les sommets portant une arête aient un degré pair.

La parité ne suffit pas sans connexité. Deux groupes d'arêtes séparés peuvent avoir uniquement des degrés pairs, mais aucun trajet continu ne couvre les deux groupes. Il faut vérifier que tous les sommets portant une arête appartiennent à une même composante connexe.

« Au plus deux » ne signifie pas quatre. Zéro sommet impair autorise un retour au départ ; deux autorisent un départ et une arrivée distincts. Avec les quatre sommets impairs de Königsberg, aucun parcours eulérien n'existe.

Les arêtes parallèles comptent séparément. Les deux ponts reliant la même paire de lieux donnent deux arêtes, pas une seule liaison simplifiée. Les fusionner changerait les degrés et ferait disparaître une partie du problème.

Un dessin différent peut représenter le même problème. Déplacer les sommets ou courber autrement les arêtes ne change pas le verdict. En revanche, ajouter, retirer ou fusionner une arête modifie le graphe et impose de recompter les degrés.

Le graphe eulérien généralise le problème en donnant le critère complet d'existence d'un parcours ou d'un circuit utilisant chaque arête une fois.

Le degré d'un sommet d'un graphe approfondit le comptage local qui rend l'impossibilité des sept ponts immédiatement visible.