Version classiqueVersion mobile

Méthodes de planification en transport

 | 
Yves Nobert
, 
Roch Ouellet
, 
Régis Parent

2. Réseaux et graphes : vocabulaire et exemples

Les formats HTML, PDF et ePub de cet ouvrage sont accessibles aux usagers des bibliothèques et institutions qui l'ont acquis dans le cadre de l'offre OpenEdition Freemium for Books. L’ouvrage pourra également être acheté sur les sites des libraires partenaires, aux formats PDF et ePub, si l’éditeur a fait le choix de cette diffusion commerciale. Si l’édition papier est disponible, des liens vers les librairies sont proposés sur cette page.

Extrait du texte

2.1 Les précurseurs

Au début du XVIIIe siècle, à Königsberg (aujourd’hui Kaliningrad, ville située dans une enclave enserrée entre la Pologne et la Lituanie et abritant le seul port russe libre de glace en hiver), des bourgeois, amateurs de questions mathématiques ou de promenades dominicales, se demandaient s’il était possible de faire un tour de ville en empruntant exactement une fois chacun des sept ponts enjambant les bras du fleuve Pregel ou conduisant à l’île de Kneiphof. Euler démontra en 1736 l’impossibilité d’établir l’itinéraire que recherchaient ces bourgeois. Son mémoire constitue la première apparition, dans la littérature scientifique, d’un graphe pour la solution d’un problème relié à la combinatoire des déplacements.

Arrêtons-nous un instant à la preuve d’Euler. La figure 2.1 donne une vue schématique à vol d’oiseau de l’emplacement des ponts de Königsberg.

Euler commença par associer, à chaque partie de la ville, un point (appelé plus loin sommet). Puis il représenta c...

© Presses de l’Université de Montréal, 2014

Conditions d’utilisation : http://www.openedition.org/6540

Acheter

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search