| |
Jean-Christophe Novelli,
chargé de recherches au CNRS, en combinatoire algébrique à l'université de
Marne-la-Vallée.
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.
|
|
