Plans de métro et réseaux neuronaux
Le 27 mai 2013 Voir les commentaires (1)
Cet article a été écrit en partenariat avec L’Institut Henri Poincaré
Lire l'article en


L’Institut Henri Poincaré et Images des Mathématiques ont uni leurs efforts pour superviser la réédition de la collection Le monde est mathématique,
publiée par RBA en partenariat avec Le Monde. En 40 ouvrages, cette collection de qualité, issue
d’un projet collectif de mathématiciens espagnols, vise à présenter,
à travers une grande variété de points de vue, de multiples facettes
des sciences mathématiques, sous un aspect historique, humain, social,
technique, culturel ...
Reprise et améliorée au niveau de la forme, cette nouvelle édition a été
entièrement lue et corrigée par l’équipe d’Images des Mathématiques ;
des préfaces et listes bibliographiques ont été ajoutées. Le Monde consacre un cahier spécial au lancement de cette collection présentée par Cédric Villani, qui en a écrit la préface générale.
Chaque semaine, à l’occasion de la sortie d’un nouveau numéro de la série,
un extrait sélectionné sera présenté sur Images des Mathématiques, suivi du sommaire du livre.
Extrait du Chapitre 3 - Graphes, circuits et optimisation
Je veux que nous envoyions un homme sur la Lune, et qu’il reviennesain et sauf sur la terre, et que cela soit fait avant la fin de la décennie.John F. Kennedy, 25 mai 1961Mon Dieu, ça y est, cette fois-ci nous devons vraiment le faire.Robert F. Freitag (NASA)
Au cours de la seconde moitié du xxe siècle, la théorie des graphes connut un spectaculaire
essor dans le domaine mathématique. Elle acquit, en outre, une nouvelle
dimension en étant intégrée à de nombreuses applications liées à la planification et
à l’optimisation. Si ce développement fut soutenu par les progrès technologiques,
notamment dans le domaine florissant de l’informatique, l’idée de trouver des solutions
optimales, en temps ou en coûts, n’avait jamais suscité jusqu’alors une telle
recherche de méthodes et d’algorithmes efficaces. Des méthodes permettant de
proposer des solutions parfaitement adaptées furent adoptées dans des domaines
aussi divers que le lancement d’Apollo II par la NASA, le ramassage des ordures et
le nettoyage des grandes villes, les chaînes de production et de distribution de voitures
ou d’aliments… La recherche opérationnelle se révéla fructueuse et la théorie
des graphes suscita un intérêt toujours d’actualité. Le présent chapitre nous invite à
envisager le potentiel de cette théorie grâce à des problèmes d’optimisation pratiques.
Les circuits eulériens
Dans un graphe connexe, trouver un circuit d’Euler (ou eulérien) revient à déterminer
s’il est possible de partir d’un sommet du graphe et d’y revenir en ne passant qu’une
seule fois par toutes les arêtes du graphe (les sommets peuvent être répétés, mais pas
les arêtes). Dans la première des figures ci-après, on peut observer un circuit d’Euler,
tandis que dans le deuxième graphe il est impossible d’en trouver un.
Euler réussit parfaitement à expliquer pourquoi un graphe connexe donné est
un circuit eulérien en étudiant le concept fondamental de degré (ou valence) d’un
sommet, qui est le nombre d’arêtes ayant une extrémité en ce sommet. La clé du
problème est donnée par le théorème d’Euler suivant :
Il convient d’ajouter qu’en cas de circuit eulérien, toute arête fera partie d’une
paire. Chaque sommet aura donc un nombre pair d’arêtes, c’est-à-dire un degré pair.
Sachant cela, après avoir compté les degrés des sommets, on sait immédiatement s’il
y a un circuit eulérien. Cependant, il peut s’avérer beaucoup plus difficile de trouver
effectivement ce circuit.
Le problème du facteur chinois
Pour réaliser une tournée idéale, un facteur intelligent qui souhaite bien faire son
travail (parcourir toutes les rues où il doit remettre du courrier) ne devra passer
qu’une seule fois dans chaque rue. (...) Ce problème ayant été
étudié par le mathématicien chinois Meigu Guan en 1962, il est connu sous le nom
de « problème du facteur chinois ».
(...)
Au-delà des tournées de facteurs, le problème (..) peut s’avérer très utile
pour tout type de livraison (ou de collecte). Dans les grandes villes, que ce soit pour
le nettoyage des rues ou les diverses livraisons commerciales, disposer d’itinéraires
intelligents est un atout particulièrement intéressant en termes de coûts et de main
d’œuvre.
L’extrait proposé est choisi par le préfacier du livre : Avner Bar-Hen. Celui-ci répondra aux commentaires éventuels.
Partager cet article
Pour citer cet article :
Claudi Alsina — «Plans de métro et réseaux neuronaux» — Images des Mathématiques, CNRS, 2013
Laisser un commentaire
Dossiers
Actualités des maths
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
-
1er avril 2022Prix D’Alembert 2022 attribué à Jean-Michel Blanquer
Commentaire sur l'article
Plans de métro et réseaux neuronaux
le 20 août 2013 à 12:07, par Audibert