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.

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.

(...)

Sommaire du livre