Les ponts de Königsberg

Source de la page: http://www.efgh.com/math/koenigsberg.htm

par Philip J. Erdelsky

9 Juin, 2015

Veuillez envoyer vos commentaires, corrections et ajouts au responsable du site Web à l’adresse [email protected]

Les ponts de Königsberg ont été résolus par le mathématicien suisse Leonhard Euler au XVIIIe siècle. C’est facile à énoncer et assez facile à résoudre.

Une rivière traverse la ville de Königsberg (aujourd’hui Kalingrad). Dans la rivière sont deux îles. Sept ponts relient les îles et les rives, comme indiqué sur cette ancienne carte:

Les deux canaux de la rivière se rejoignent quelque part du côté droit de la carte.

De nombreuses personnes ont essayé de faire le tour de Königsberg en traversant chaque pont une fois et une seule fois, mais personne ne pouvait le faire. Euler a montré que la tâche est impossible. Sa preuve ne nécessite que des connaissances de base en arithmétique et en propriétés des nombres pairs et impairs.

La brillante idée d’Euler, si vous pouvez l’appeler ainsi, consistait à compter le nombre de ponts connectés à chaque bout de terrain:

– 3 sur la rive nord
– 3 sur la rive sud
– 5 sur l’île au centre de la carte
– 3 sur l’île à droite de la carte

Une promenade qui traverse chaque pont une fois et une seule fois s’appelle, assez convenablement, une promenade d’Euler (ou un chemin d’Euler).

Si une promenade Euler ne commence pas ou ne se termine pas sur un terrain particulier, il doit alors y avoir un même nombre de ponts qui y sont connectés, car un promeneur Euler qui pénètre dans la zone par un pont doit le quitter par un autre. Si une marche Euler commence ou se termine sur un terrain particulier, le nombre de ponts qui y sont connectés doit être ODD.

Étant donné que chacun des quatre terrains est relié à un nombre impair de ponts, il est évident qu’une promenade en Euler est impossible.

Les ponts de Königsberg sont un exemple de structure mathématique générale appelée graphe.

Un graphe est constitué d’un nombre fini de sommets (également appelés nœuds), correspondant aux portions de terrain des ponts de Königsberg, et d’un nombre fini d’arêtes (également appelées lignes), correspondant aux ponts. Nous continuerons à les appeler des ponts. De plus, pour éviter des difficultés avec des parcours inexistants, nous exigeons qu’il y ait au moins un sommet.

Voici une représentation plus abstraite du graphique de Königsberg:

Un graphique peut être plus général que les ponts de Königsberg. Par exemple, un pont peut connecter un sommet à lui-même et les sommets ne doivent pas nécessairement être limités à un seul plan. Un sommet isolé, sans ponts de connexion, est également possible.

Le nombre de ponts reliant un sommet particulier est appelé son degré (ou valence).

Les arguments d’Euler ont montré qu’une marche d’Euler n’est possible que si (1) tous les sommets sont de degré pair, auquel cas la marche commence et se termine au même sommet, ou (2) deux sommets, où la marche commence et se termine, sont de degré impair et tous les autres sommets sont de degré pair.

Deux propriétés des promenades d’Euler sont évidentes. Le revers d’une marche d’Euler est une marche d’Euler. Si une marche d’Euler commence et se termine au même sommet, elle peut également être commencée et terminée à n’importe quel autre sommet.

Ces conditions sont-elles également suffisantes? Évidemment pas. Le graphique doit également être connecté, c’est-à-dire qu’il doit exister un chemin (pas nécessairement un chemin d’Euler) de chaque sommet à un autre sommet.

Prouver l’existence d’une marche d’Euler pour un graphe connecté sans sommets de degré impair ou deux sommets de degré impair est un peu plus difficile, mais cela n’implique aucune mathématique avancée.

Tout d’abord, considérons un graphe connecté où tous les sommets sont de degré égal. Commencez à marcher à un sommet, en gardant une trace des ponts que vous avez traversés. Chaque fois que vous entrez dans un sommet, laissez-le près d’un pont que vous n’avez pas encore traversé. Si ce n’est pas le sommet de départ, si vous êtes entré par un pont non croisé, vous pouvez toujours le laisser par un autre. Et après votre départ, le sommet a toujours un nombre pair de ponts non croisés.

La promenade doit prendre fin lorsque vous revenez au sommet de départ et vous ne pouvez pas trouver un pont non croisé pour le quitter.

Si vous avez réussi à traverser tous les ponts, la marche est terminée.

S’il y a toujours au moins un pont non croisé, la promenade doit être augmentée.

Notez cependant que chaque sommet a toujours un nombre pair de ponts non croisés.

Le graphique étant connecté, il existe un chemin du sommet au sommet à un sommet avec un pont non croisé. Considérez le premier sommet de cette trajectoire avec un pont non croisé. Ce doit être dans la promenade. Appelez ça le sommet A.

Commencez maintenant au sommet A et faites une deuxième promenade en ne traversant que les ponts que vous n’avez pas encore traversés, que ce soit dans cette promenade ou dans la première. Comme précédemment, la marche ne se termine que lorsque vous revenez au sommet A.

Maintenant, combinez les deux promenades en une seule promenade. Pour ce faire, le plus simple consiste à commencer par marcher au sommet A. Lorsque vous revenez au sommet A, faites la deuxième promenade.

S’il y a toujours au moins un pont non croisé, vous pouvez poursuivre ce processus jusqu’à ce que tous les ponts aient été traversés.

Vous pourriez vous demander ce qui se passe si le graphique ne comporte qu’un sommet et au moins un pont. Il est facile de montrer que le graphique est connecté, que le sommet a même degré et qu’il existe une marche d’Euler. Un graphique avec un seul sommet et aucun pont ne constitue pas nécessairement une exception, bien que les concepts de connectivité et de parcours d’Euler soient quelque peu vides dans ce cas.

C’est le résultat souhaité pour un graphe connecté dans lequel chaque sommet est de degré pair. Considérons maintenant un graphique avec deux sommets B et C de degré impair. Créez un graphique légèrement plus grand en insérant un pont reliant les sommets B et C. Tous les sommets de ce graphique sont de degré pair, il a donc une marche d’Euler. Une partie de cette marche consiste à traverser le nouveau pont du sommet B au sommet C, ou inversement.

Il est clair que cette marche d’Euler, sans le nouveau croisement entre les sommets B et C, est une marche d’Euler sur le graphique d’origine.


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *