Plans de métro et réseaux neuronaux

27 mai 2013  - Ecrit par  Claudi Alsina Voir les commentaires (1)

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

Cet article a été écrit en partenariat avec RBA

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 revienne
sain et sauf sur la terre, et que cela soit fait avant la fin de la décennie.
John F. Kennedy, 25 mai 1961
 
Mon 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.

PNG - 23.8 ko

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 :

« Un graphe connexe contient un circuit eulérien si et seulement si tous ses sommets ont un degré pair. »

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.

(...)

PDF - 1.5 Mo
Sommaire du livre
Post-scriptum :

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

Commentaire sur l'article

  • Plans de métro et réseaux neuronaux

    le 20 août 2013 à 12:07, par Audibert

    Dans le livre N°10 est présenté le très joli problème des ponts de Könisberg .Il n’y a aucune honte à chercher à faire l’inventaire pas à pas de tous les chemins possibles (des centaines de chemins). C’est une recherche que peut pratiquer quelqu’un qui ne connaît pas le graphe de la page 17. Le raisonnement par l’absurde sur la parité des chemins ne viendra que beaucoup plus tard et en sera d’autant plus probant . Un des charmes de cette collection vient des petits problèmes proposés qui sont ,de plus ,fondamentaux pour la construction des mathématiques. G.A.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Cartographie» voir le dossier
Cet article fait partie du dossier «Le monde est mathématique» voir le dossier

Suivre IDM