LE JEU DES PONTS ET DES ILES

Parmi les divers travaux des mathématiciens sur cette branche de la science de l'étendue que Ton nomme Géométrie de situation, on rencontre, dès l'origine, un fameux Mémoire d'Euler, connu sous le nom de Problème des Ponts de Kœnigs berg; nous donnons ci-dessous, d'après la traduction de M. C. Henry, un commentaire de cet opuscule, qui a paru en latin dans les Mémoires de V Académie des sciences de Berlin pour Tannée 1759, et qui a pour titre : Solutio problematis ad Geometriam situs pertinents.

ara»*.

"LE MÉMOIRE d'eULER.

i° Outre cette partie delà Géométrie qui s'occupe de la grandeur et de la mesure, et qui a été cultivée dès les temps les plus reculés, avec une grande application, Leibniz a fait mention, pour la première fois, d'une autre partie encore très inconnue actuellement, qu'il a appelée Geometria situs. D'après lui, cette branche

Deuxième récréation.

de la science s'occupe uniquement de l'ordre et de la situation, indépendamment des rapports de grandeur. Mais quels sont les problèmes qui appartiennent à cette géométrie ; quelles sont les méthodes qu'il faut employer a leur résolution? C'est ce qui n'a pas encore été nettement défini. Récemment j'ai entendu parler d'un problème qui paraît se rapporter à la Géométrie de situation, puisqu'il ne contient, dans son énoncé, que des considérations d'ordre et non de mesure ; aussi ai-je résolu d'exposer ici, comme un spécimen, la méthode que j'ai trouvée pour résoudre ce problème. ■

2° A Kcenigsberg, en Poméranie, il y a une île appelée Kneip-

Ao/;le fleuve qui l'entoure se divise en deux bras [fi g. i), sur les-

Fig. i.

Les ponts de Kcenigsberg

quels sont jetés les sept ponts a, b, c, d, e,f, g. Gela posé, peuton arranger son parcours de telle sorte que l'on passe sur chaque

Le jeu des ponts et des îles. 23

pont, et que Ton ne puisse y passer qu'une seule fois? Cela semble possible, disent les uns ; impossible, disent les autres ; cependant personne n'a la certitude de son sentiment. Je me suis donc proposé le problème suivant, qui est très général :

Quelle que soit la forme d'un fleuve, sa distribution en bras, par des îles en nombre quelconque, et quelque soit le nombre des ponts jetés sur le fleuve, trouver si l 'on peut franchir celui-ci en passant une fois, et une seule, sur chacun des ponts.

3° Quant au problème particulier des sept ponts de Kœnigsberg, on pourrait évidemment le résoudre en faisant Pénumération complète de tous les parcours possibles ; on reconnaîtrait ainsi s'il existe ou non un chemin qui réponde à la question. Mais, par suite du grand nombre de permutations, cette méthode, déjà difficile et laborieuse dans le cas particulier, serait impraticable pour un plus grand nombre de ponts ; d'autre part, parmi ces permutations, beaucoup d'entre elles sont inutiles, de telle sorte qu'après avoir terminé l'opération on aurait rencontré un grand nombre de choses qui ne sont pas en question ; c'est en cela, sans aucun doute, que réside la cause d'une aussi grande difficulté (' ). Donc, en laissant de côté ces considérations, j'ai recherché s'il n'était pas préférable d'imaginer une méthode qui permît de juger, au premier abord, de la possibilité ou de l'impossibilité du problème ; je pensais, en effet, qu'une telle méthode devait être beaucoup plus simple (*).

{ * ) C'est pour la même raison, très probablement, que Ton n'a pas encore trouvé la solution du problème des reines lorsque le nombre de celles-ci dépasse huit; voir à ce sujet notre quatrième récréation sur le problème des huit reines au jeu des échecs. Quant aux permutations qu'il y aurait Heu de considérer ici, ce sont les permutations avec répétition.

(*) Cette remarque d'Euler comporte un très grand caractère de généralité qu'elle ne paraît pas avoir toutd'abord. J'ai observé que, dans un grand nombre