Topologie: ponts, îles et traversées en bateau

chou

il manque la chèvre et le loup

Ménager la chèvre et le chou

Lorsqu’il n’y a pas de pont, on est parfois bien embarrassé.

Tout le monde connaît le problème suivant:  il s’agit de passer sur l’autre rive d’une rivière un loup, une chèvre et un chou dans un bateau si petit que seul le batelier et l’un de ceux qu’il doit transporter peuvent tenir. Comment s’y prendre pour que le loup ne soit pas un seul instant sur l’un des bords avec la chèvre qu’il dévorerait et que celle-ci ne soit pas un seul instant avec le chou qu’elle dégusterait.

 

Les ponts et les îles

Les ponts de Königsberg en en 1739

Les ponts de Königsberg en en 1739

Euler et Leibnitz ont étudié les cas dans lesquels il est possible de franchir un fleuve en passant une seule fois sur chacun des ponts qui relient ses rives entre elles ou à des îles ou qui relient les îles entre elles. C’est ainsi qu’Euler fonda la topologie.

On compte combien de ponts aboutissent sur chaque rive du fleuve ou sur chaque île: on note les différents totaux et le problème est impossible quand on trouve plus de deux totaux impairs.

Il est possible dans deux cas:

1 – quand tous les totaux sont pairs et alors le point de départ peut être arbitraire d’une région quelconque.

2 – lorsqu’il y a deux totaux impairs. Le point de départ doit alors se trouver sur une région où aboutit un nombre impair de ponts et le point d’arrivée sur une région où aboutit un nombre pair de ponts ou inversement.

Les ponts de l'île Saint-Louis et de la Cité et le pont des arts

Les ponts de l’île Saint-Louis et de la Cité et le pont des arts

Dans ce dernier cas, pour trouver la route à suivre, on supprime, par la pensée les couples de ponts qui conduisent d’une région dans une autre et on cherche le chemin à suivre avec ceux qui restent. Puis on rétablit les ponts supprimés.

Les deux schémas montrent un cas insoluble et un cas soluble. A vous de trouver les solutions avec les explications ci-dessus.

Je vous conseille d’effectuer le trajet réellement et à pied, c’est tellement beau : on peut traverser tous les ponts de Paris en passant une seule fois sur chaque pont, mais à condition de toujours commencer par l’île Saint-Louis ou y aboutir.

Laisser un commentaire

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

Anti-Spam Quiz: