Planos del metro y redes neuronales
Le 27 mai 2013Le 10 août 2020
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
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.
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 :
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.
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
Laisser un commentaire
Dossiers
Actualités des maths
-
7 avril 2021Les maths dans la musique... la musique des maths (en ligne, 8/4)
-
16 mars 2021Des signaux partout – Des chauves-souris à Internet (en ligne, 25/3)
-
11 mars 2021Mathématiciens engagés : regards croisés (en ligne, 16/3)
-
10 mars 2021Astigmath, un quiz culturel pour tous et toutes (14/3)
-
8 mars 2021Cinquième édition du festival « Les maths dans tous leurs états »
-
23 février 2021Courbes et surfaces : le monde de Maryam Mirzakhani (Twitch, 1/3)
Commentaire sur l'article