LES PONTS DE KÖNIGSBERG
Accueil Remonter LES PONTS DE KÖNIGSBERG LES GRAPHES PLANAIRES LE COLORIAGE DES CARTES POUR CONCLURE

 

 

    Léonhard Euler est un mathématicien Suisse, né à Bâle en 1707 et mort à Saint Pétersbourg en 1783. Personnage d'exception, ses contributions pour les mathématiques sont remarquables. Il occupera la chaire de mathématique de St. Pétersbourg, fera un tour par l'académie de Berlin et reviendra en Russie où il finira ses jours. Vers 1733, il perd l'usage d'un oeil, en 1771 il devient aveugle, mais continue à travailler grâce à l'aide de son fils aîné Jean-Albert (L'un des 13 fils de l'illustre professeur, dont 8 sont morts en bas âge).

    L'histoire des ponts ne montre qu'une infime partie du travail qu'à réalisé Euler. L'anecdote est la suivante, le Parc de Königsberg est constitué d'une île entourée par 7 ponts. La question était de savoir s'il existait un trajet permettant de ne franchir qu'une seule fois chaque pont. Comme pour les maisons, il semblait que cela soit impossible, mais personne ne l'avait prouvé.

 

 

    C'est là qu'Euler intervient, en créant une nouvelle branche des mathématiques : la théorie des graphes. La rivière, l'île la presqu'île, les berges et les ponts sont remplacés par des arcs, des segments et des lettres, moins poétiques certes, mais beaucoup plus efficaces. Les points a, b, c et d, constituent les sommets du graphe, et correspondent à chacun des sites du parc. les arcs et les segments qui relient chacun des sommets, représentent les 7 ponts.

    La question est de savoir maintenant si l'on peut trouver un chemin passant par chaque sommet, en empruntant qu'une seule fois chaque arc ou segment. Un tel chemin, si il existe, est appelé chemin eulérien.

    Alors, comment savoir s'il existe un chemin eulérien pour les ponts de Königsberg ( aujourd'hui Kaliningrad)? Là le plus simple c'est encore de faire confiance à Euler, et à son concept de degré d'un sommet du graphe, c'est à dire le nombres de segments ou (et) d'arcs partant de ce sommet. Donc, il existe un chemin eulérien si et seulement si, à l'exception du sommet de départ et du sommet d'arrivée, tous les sommets sont de degré pairs.

    Et voilà, pas de chemin eulérien pour les promeneurs de Königsberg, si lors de vos prochaines vacances en Russie, vous poussez jusqu'à Kaliningrad, et que vous voyez quelqu'un passer ses journées à traverser et retraverser les ponts, abrégez ses souffrances, prenez un papier, un crayon et montrez lui le graphe, tous les sommets sont impairs, il n'a vraiment aucune chance.

    Bon très bien me direz vous, mais quid de nos maisons? Ce type de graphe ne permet pas de résoudre notre problème c'est vrai, mais malgré tout, on sent qu'on s'approche de la solution, il faut des graphes qui prennent en compte les croisements de liens entre chaque sommet. Je vous sent perplexe, et bien vous avez tort, de tels graphes existent bel et bien, ce sont les graphes planaires. C'est formidable non!?

    Mais avant d'aller plus loin, une petite question tout de même : combien faudrait-il rajouter de ponts, pour obtenir un chemin eulérien? Mais au fait, peut-on obtenir un chemin eulérien en rajoutant des ponts?

nts?