Königsberg était une ville de Prusse orientale traversée par un fleuve. Ce fleuve se divisait en deux cours d'eau pour laisser apparaître une île dans la ville et ainsi découper la ville en 4 quartiers reliés entre eux par 7 ponts.
Le problème des ponts de Königsberg fût alors posé: " est-il possible de traverser les 7 ponts une unique fois au cours d'une même promenade? "
Plusieurs tentatives furent un échec mais du fait du très grand nombre de chemins possibles, ils était difficile de tous les essayer.
Finalement, c'est Leonhard Euler qui a résolu ce problème en 1736.
Leonhard Euler était un mathématicien et scientifique suisse du 18ème siècle, considéré comme l'un des plus grands spécialistes des mathématiques de son temps.
Parmis ses contributions les plus importantes, on peut citer l'introduction de la fonction gamma ou encore l'analogie entre le calcul infinitésimal et le calcul des différences finies.
Il est aussi à l'origine du développement de la méthode des algorithmes avec laquelle il est parvenu, par exemple, à prédire les phases de la lune, afin d'obtenir des informations pour la préparation de tableaux destinés à aider le système de navigation.
Afin de simplifier son travail, Euler commença par tracer une représentation simplifiée de la ville en ne conservant que les 4 quartiers et les 7 ponts les reliant les uns aux autres.
Voici un schéma résumant la situation:
Sur le schéma, les 4 quartiers sont représentés par les lettres A, B, C et D.
On peut même aller plus loin dans la simplification et représenter la situation par le graphe suivant:
Un graphe est un objet mathématique se composant de sommets (ici les lettres A, B, C et D représentant les quartiers) et d'arêtes (ici numérotées de 1 à 7 représentant les 7 ponts).
Pour chaque arête \( i\), on associe l'ensemble \(s_i\) de ses sommets.
Par exemple, on aura \( s_3=\{C;B\} \) puisque le pont numéro 3 relie les quartiers C et B.
Sur un graphe, pour énoncer un chemin emprunté, on le donne sous la forme \( s_0 c_0 s_1c_1...s_nc_n \).
Par exemple, pour aller de A vers B, un chemin possible serait A 2 C 4 B, autrement dit le chemin partant de A, passant par le pont 2 pour arriver à C puis qui emprunte le pont 4 pour aller vers B.
On parle de chemin eulérien dans un graphe lorsque le chemin emprunte chaque arête une et une seule fois, autrement dit, le problème posé par les ponts de Königsberg qui peut être résumé de la façon suivante: dans le graphe précédent, existe t-il un chemin eulérien?
En 1735, Euler démontra que ce n'était pas possible.
Pour le démontrer, nous allons avoir besoin d'une nouvelle notion: le degré d'un sommet qui est en fait le nombre d'arêtes qui atteignent ce sommet.
On aura donc, par exemple, le degré du sommet A qui vaut 3 car 3 chemins "touchent A" que l'on peut noter \( d(A)=3 \).
On peut désormais introduire le théorème d'Euler:
"Si un graphe G possède un chemin eulérien alors le nombre de sommets de degré impair est soit 0 soit 2.
De plus, si ce nombre est 0 alors tout chemin eulérien sur G est fermé (l'arrivée est le point de départ), et sinon tout chemin eulérien part d’un des sommets de degré impair et aboutit à l’autre."
Dans notre graphe, on a \( d(A)=d(B)=d(C)=3\) et \( d(D)=5\).
Ainsi, notre graphe possède 4 sommets de degré impair donc on en déduit qu'il n'existe pas de chemin eulérien dans ce graphe donc il n'est pas possible d'emprunter un chemin passant par chaque pont une unique fois (cette déduction se fait par l'absurde: on suppose qu'il existe un chemin eulérien donc on doit avoir présence de 0 ou 2 sommets de degré impair, condition non respectée).
On vient de voir que la présence d'un chemin eulérien dans un graphe entraîne la présence de 0 ou 2 sommets de degré impair.
On peut donc se poser la question de savoir si la présence de 0 ou 2 sommets de degré impair entraîne forcément l'existence d'un chemin eulérien.
En fait, la réponse est évidemment non, il suffit de prendre le graphe suivant pour s'en rendre compte
Il est évident, dans ce graphe, que nous ne pourrons pas relier tous les chemins et pourtant on a bien 0 sommet de degré impair donc avoir 0 ou 2 sommets de degré impair n'implique pas forcément la présence d'un chemin eulérien.
On pourrait préciser le contexte en se demandant s'il existe un chemin eulérien lorsque l'on a 0 ou 2 sommets de degré impair dans un graphe connexe (à partir de chaque sommet, il est possible de trouver un chemin pour relier n'importe quel autre sommet ).
Je vous laisserai réfléchir à ce cas de figure!
“Les mathématiques ne révèlent leurs secrets qu'à ceux qui les abordent avec pur amour, pour leur propre beauté.”
Archimède, Mathématicien, Physicien, Scientifique
La Maths-inale pour cartonner en Maths au lycée.
Une méthode structurée qui vous donne les clés pour faire exploser votre progression et vos notes en Maths, en 1ère et en Terminale.