Le jeu du voyageur de commerce
Article mis en ligne le 6 août 2009
Imprimer logo imprimer

Voir la conférence

Le jeu du voyageur de commerce : la théorie des graphes
par Jean-Christophe Novelli chargé de recherches au CNRS, en combinatoire algébrique àl’université de Marne-la-Vallée.

Cette conférence a été donnée le 11 décembre 2004 àla cité des sciences. Elle dure 1h30 et s’adresse plus particulièrement aux élèves de ES.


Résumé

Un voyageur de commerce, un réparateur de machines àlaver, et un déménageur ont tous la même question àrésoudre : comment faire pour aller àtous ses rendez-vous sans parcourir une distance excessive ?
Le jeu des circuits sur lequel se fonde la conférence est un cas très particulier du problème du voyageur de commerce. O le pays a une forme rectangulaire (m cases par n), les lieux de rendez-vous étant représentés par les milieux de chaque case et la distance entre deux villes voisines constante. Le jeu consiste àcréer un parcours passant par chaque ville en revenant àson point de départ. On verra qu’il existe de nombreuses solutions àce problème et que la question de leur énumération pose des problèmes de description, de codage, et nous amène directement dans les mondes de la combinatoire, des mathématiques et de la physique mathématique.


 
 
 
 

Calendrier

Évènements à venir

Dernières actus



puce Plan du site puce Contacts puce Mentions légales puce

RSS Valid XHTML 1.0 Strict

2004-2017 © Lycée Jacques Monod - Tous droits réservés
Site réalisé sous SPIP
avec le squelette ESCAL-V3
Version : 3.79.3