Planos del metro y redes neuronales

Le 27 mai 2013  - Ecrit par  Claudi Alsina
Le 10 août 2020  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Plans de métro et réseaux neuronaux Voir les commentaires
Lire l'article en  

El Instituto Henri Poincaré e Images des Mathématiques han unido sus esfuerzos para supervisar la reedición de la colección El mundo es matemático, publicada por RBA en convenio con Le Monde. En 40 obras, esta colección de calidad -resultado de un proyecto colectivo de matemáticos españoles- aspira a presentar, a través de una gran variedad de puntos de vista, de múltiples facetas, las ciencias matemáticas bajo un aspecto histórico, humano, social, técnico, cultural...
Revisado y mejorado al nivel de la forma, esta nueva edición fue completamente leída y corregida por el equipo de Images des Mathématiques. Fueron agregados prefacios y listas bibliográficas. Le Monde dedica un suplemento especial para el lanzamiento de esta colección, presentada por Cédric Villani, quien escribió el prefacio original.
Cada semana, con la salida de un nuevo número de la serie, un extracto seleccionado será presentado en Images des Mathématiques. Será acompañado por un índice del libro y una invitación a prolongar su lectura.

Extracto del Capítulo 3 - Grafos, circuitos y optimización

Deseo que enviemos un hombre a la Luna y lo traigamos de vuelta a la Tierra sano y salvo, y que eso se haga antes del fin de esta década.
John F. Kennedy, 25 de mayo 1961

Dios mío, ya está, ahora realmente tenemos que hacerlo.
Robert F. Freitag (NASA)

En el curso de la mitad del siglo XX, la teoría de los grafos tuvo un espectacular auge en el campo matemático. Adquirió además una nueva dimensión al ser integrada a numerosas aplicaciones ligadas a la planificación y a la optimización. Si este desarrollo fue sostenido por los progresos tecnológicos -especialmente en el floreciente campo de la informática- la idea de encontrar soluciones óptimas, en tiempo o en costos, nunca hasta ahora había suscitado tal búsqueda de métodos y algoritmos eficaces. Fueron adoptados métodos que permitieran proponer soluciones perfectamente adaptadas a campos tan diversos como el lanzamiento de la Apolo 11 por la NASA, la recolección de basuras y aseo de grandes ciudades, o las cadenas de producción y de distribución de automóviles o de alimentos… La investigación operacional se reveló fructífera y la teoría de grafos suscitó un interés siempre de actualidad. El presente capítulo nos invita a proyectar el potencial de esta teoría gracias a problemas prácticos de optimización.

Los circuitos eulerianos

En un grafo conexo, encontrar un circuito de Euler (o euleriano) se traduce en determinar si es posible partir de un vértice del grafo y volver pasando solo una vez por todas las aristas del grafo (los vértices pueden repetirse pero no las aristas). En la primera de las figuras a continuación, se puede observar un circuito de Euler, mientras que en el segundo grafo es imposible encontrar uno.

PNG - 23.8 ko

Euler logró perfectamente explicar por qué un grafo conexo dado es un circuito euleriano, estudiando el concepto fundamental de grado (o valencia) de un vértice, que es el número de aristas que tienen un extremo en ese vértice. La clave del problema está dada por el siguiente teorema de Euler :

’’Un grafo conexo contiene un circuito euleriano si y solamente si todos sus vértices tienen un grado par.’’

Conviene añadir que en caso de un circuito euleriano, toda arista será parte de un par. Cada vértice tendrá entonces un número par de aristas, es decir, un grado par. Sabiendo eso, después de haber contado los grados de los vértices, se sabe inmediatamente si hay un circuito euleriano. Sin embargo, puede resultar mucho más difícil encontrar efectivamente ese circuito.

El problema del cartero chino

Para realizar un recorrido ideal, un cartero inteligente que desea hacer bien su trabajo (ir por todas las calles donde debe entregar la correspondencia) no deberá pasar más que una sola vez por cada calle. (...) Ese problema, que fue estudiado por el matemático chino Meigu Guan en 1962, es conocido bajo el nombre de ’’problema del cartero chino’’.

(...)

Más allá de los recorridos de los carteros, el problema (..) puede resultar muy útil para todo tipo de entregas (o de recolecciones). En las grandes ciudades, ya sea para la limpieza de las calles o los diversos repartos comerciales, disponer de itinerarios inteligentes es una ventaja especialmente interesante en términos de costos y de mano de obra.

(...)

PDF - 1.5 Mo
Sommaire du livre
Post-scriptum :

El extracto propuesto fue elegido por el autor del prefacio del libro Avner Bar-Hen. Él responderá los eventuales comentarios.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Planos del metro y redes neuronales» — Images des Mathématiques, CNRS, 2020

Commentaire sur l'article

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 «Cartografía» voir le dossier
Cet article fait partie du dossier «El mundo es matemático» voir le dossier