Réalisateur : Jean Luc Léon

Mathématicien : Jean Michel Kantor (Paris VII)

Thème : Théorie des graphes et recherche opérationnelle. Comment des problèmes d’organisation peuvent-t-ils être résolus sous l’angle des mathématiques ?

Un maire d’un petit village 1900, désolé de voir ses administrés gâcher leurs énergies, décide une campagne d’information.

Premier problème

Comment le facteur peut-il faire sa tournée en n’empruntant qu’une seule fois chaque rue ? Ce problème, dit problème eulérien (analogue à celui des » ponts de Kœnigsberg), ne peut être résolu que si aucun carrefour ne comporte un nombre impair de rues : ici le problème est impossible car un carrefour du petit village est le point de •

Deuxième problème A l’occasion d’un pique-nique, comment faire traverser trois couples de la rive gauche à la rive droite, au moyen d’une barque ne pouvant contenir que deux personnes, sachant que les maris sont très jaloux (surtout monsieur Folichon) et ne peuvent concevoir que leur épouse reste sur une rive ou sur le bateau, seule en présence d’un autre homme ?

Ce problème peut être résolu par la théorie des graphes, au moyen de 11 traversées : si on représente la situation sur la rive gauche par un point de coordonnées (homme, femme) la situation initiale est (3,3) et la finale est (0,0). La solution est représentée sur la figure ci-après.

On la détermine en plaçant les seuls points possibles compte-tenu des contraintes de jalousies et on cherche les jonctions possibles.

Cette démarche est utilisée pour l’étude des réseaux de transport.

 

Le troisième problème est celui de la recherche par le facteur du trajet le plus court pour le relevé des boîtes aux lettres. Pour un petit village avec 7 boîtes aux lettres il y a 350 trajets possibles qu’il faudrait tous tester car ce problème n’est pas encore résolu. Pour un nombre de rues plus élevé, tous les ordinateurs les plus puissants de la terre ne suffiraient pas : c’est un exemple de problème simple qui n’est pas résolu à l’heure actuelle. On pense qu’il n’y a pas de solution. On a seulement déterminé des solutions approchées.

Ce film a l’avantage de l’unité de lieu et de montrer comment résoudre des problèmes faciles à comprendre. Les trajets du facteur sont un peu lents mais bien agrémentés, pour rompre la monotonie.

Pour en savoir plus :

Sur les théories des graphes.

1. Berge, Théorie des graphes et ses applications, Dunod, 1958.
2. Berge, Graphes et hypergraphes, Gauthier-Villars, 1970.
3. Grossman, W. Magnus, Les groupes et leurs graphes, Dunod 1971.

Le premier problème fut résolu par Leonhard Euler (1707 – 1783) en 1736 pour la ville de Königsberg (Kaliningrad aujourd’hui), traversée par la Pregel, rivière qui coule de part et d’autre de l’île de Kneiphof et qui possède sept ponts. Un piéton ne peut se promener en traversant une fois et une seule chaque pont car il y a cinq ponts aboutissant à l’île.

Le deuxième problème est celui d’Al Quinn (réincarnation du mathématicien médiéval Alcuin ([735 – 804]) où un agriculteur doit faire traverser une rivière à un lion, un lama et une laitue. C’est aussi le problème du loup, de la chèvre et du chou. Ce problème est mentionné très tôt par exemple dans l’ouvrage d’Ozanam, Récréations mathématiques (1694). Une étude proposée par I. Stewart dans Pour la Science,  1989, p. 102 à 107.

Pour le troisième problème, celui du réseau le plus court, on pourra consulter Le calcul inter-sif (Bibliothèque pour la Science, 1989, p. 10:

109, Distribution Belin). L’algorithme de recherche du réseau le plus court est celui de Steiner. La méthode de l’ordinateur à bulle de savon, utilisant la propriété de surface minimale de Plateau, permet pratiquement d’obtenir une solution du problème à vingt-neuf points, ce qui semble être la limite des ordinateurs actuels (voir aussi Les mathématiques d’aujourd’hui, Bibliothèque pour la Science, Diffusion Belin, 1986, p. 168 à 182).