Reflexiones y aplicaciones
¿Para qué sirve la teoría de gráficas?
Optimización de recorridos
Como has visto, una de las aplicaciones de la teoría de gráficas es la optimización de recorridos en mapas, por ejemplo, en rutas turísticas, para encontrar una ruta en la que no se recorra ningún camino más de una vez y se visiten todos los puntos de interés, si es que ésta existe.
En mayo de 2010, la Secretaría de Turismo de México lanzó el programa “Las 10 Rutas de México“, con el fin de ofrecer a los turistas nacionales y extranjeros la oportunidad de combinar su visita a los destinos de sol y playa con el amplio patrimonio histórico y cultural de México y así promover la actividad turística en el país. La ruta 8, “El misterio y el origen de los mayas” es un recorrido por los vestigios arqueológicos de la Civilización Maya. Incluye también las ciudades coloniales de Campeche y Mérida, testimonios de la arquitectura de estilo barroco traída por los españoles. Los destinos de esta ruta son: Villahermosa, Palenque, Campeche, Uxmal, Mérida, Chichén Itzá y Cancún. Sin embargo, hay múltiples destinos cercanos a estas ciudades, además de varias rutas para visitarlos, como lo ilustra el siguiente mapa de la zona:

Tarea
Imagina que eres un agente de viajes y estás planeando un tour por los destinos que están enmarcados en naranja en el mapa de arriba. Para hacer el recorrido lo más atractivo posible, y para no gastar innecesariamente en gasolina, te propones nunca regresar sobre tus pasos, es decir, recorrer cada camino no más de una vez. Además eres prudente, así que decides sólo tomar los caminos que estén seguros y se encuentren en buen estado (los de color cáfe, azul y naranja).
A. En un inicio, tu plan es hacer base en la ciudad de Valladolid y desde ahí emprender pequeñas excursiones de un día.
- ¿Cuántos de los destinos señalados en el mapa se pueden visitar bajo las condiciones señaladas?
- ¿Cómo representarías esta situación mediante una gráfica como la que elaboró Euler?
- ¿A qué tipo de gráfica euleriana corresponde el plan descrito?
B. Rápidamente te das cuenta de que tu plan inicial está condenado al fracaso. Ahora optas por un solo recorrido partiendo de un punto aún por determinar y pasando por la mayor cantidad de destinos posible, nuevamente sin repetir rutas.
- ¿Cuántos de los destinos señalados en el mapa es posible visitar con esta nueva estrategia?
- Elabora una gráfica y explica, en términos 'eulerianos', por qué es así.
C. Ahora supongamos que los gobiernos de los estados donde se encuentran estos puntos de interés quieren construir carreteras para extender la red de rutas turísticas. ¿Qué carreteras se deberían de construir para poder realizar los trayectos que se señalan a continuación, sin repetir caminos? Considera que las obras se deben realizar al menor costo posible, es decir, cubriendo la menor distancia posible con las carreteras que se van a construir. Nuevamente, apóyate en la teoría de grafos para justificar tus recomendaciones.
Recorridos que se deberían de poder realizar gracias a la extensión de la red vial:
- Tour El vago: dos pequeñas excursiones desde Valladolid, visitando tres destinos cercanos a esta ciudad.
- Tour De paso: un solo trayecto pasando por Valladolid y otros 4 destinos cercanos.
- Tour El aventurero: un gran recorrido de varios días que inicia y termina en Valladolid, pero sin pasar por esta ciudad durante el recorrido.
Para buscar las respuestas a las preguntas, puedes usar las herramientas interactivas de siempre.