Introducción

Los ciudadanos se sentían muy orgullosos de esta gran red de comunicación, y entre ellos surgió un pequeño juego para entretenerse en los momentos de aburrimiento. Solo consistía en una sola pregunta: ¿Se puede pasar por todos los puentes pasando una sola vez por cada puente? Piensa un momento esa pregunta y debate. 

¿Cómo lo solucionó Euler? Como primer paso simplificó el mapa de la siguiente manera: 

Como podemos ver, los distintos territorios en los que los puentes dividieron la ciudad se convirtieron en puntos, es decir, en «vértices»; y los puentes se convirtieron en líneas, lo que llamamos «aristas». También determina que hay un punto de «inicio» y un punto de «salida». Euler consiguió, a partir de este sencillo esquema, encontrar la solución de una forma mucho más elegante. 

Para poder recorrer un sistema de este tipo, los vértices «intermedios» deben tener un número par de aristas. Es decir, deben tener una vía para entrar y una vía para salir. Sólo los puntos de inicio y salida pueden tener un número impar de aristas, porque, evidentemente, nunca «entramos» al punto de inicio y nunca «salimos» del punto de llegada. Lo que nos lleva a la conclusión de que es imposible pasar por todos los puentes recorriendolos una sola vez. 

Este es uno de los problemas que dio pie al desarrollo de teoria de redes, es por ello que a continuación abordaremos definiciones y algoritmos importantes para la solución de esta práctica. 

Para las siguientes situaciones se utilizará la red del metro de la CDMX parcialmente 

Situación 1: Internet en el metro

Se tiene una red con únicamente los transbordo de la red del metro Se requiere poner fibra óptica con internet en todos los transbordos de la red con costo mínimo ¿Cúal sería el costo de este proyecto? Condiciones de trabajo: para esta red sólo considera como nodos las estaciones de las líneas que se intersectan con otras, es decir, las estaciones que tengan transbordos; para darle valor a las aristas toma el número de estaciones que hay entre cada transbordo, si las estaciones son contiguas da el valor de ½. 

Situación 2: Distancias. 

En esta ocasión la red del metro se reduce a las primeras ocho líneas. Si se quiere ir desde la estación Cuatro caminos hasta Pantitlán en el menor tiempo posible ¿Cuál es la ruta indicada?. Considera también que se quiere viajar desde Cuatro caminos hasta Santa Anita ¿Cuál es el tiempo mínimo de recorrido? Condiciones de trabajo: en esta red considerarán las líneas de la uno a la ocho, las estaciones de inicio y fin de cada línea así como los transbordos que hay entre ellas para poder definir el número de nodos. Suponiendo que el tiempo de recorrido entre dos estaciones es de 2 minutos aproximadamente, calcula el tiempo que hay entre nodos. 

Considera la siguiente red dirigida

Situación 3: ¿se saturará alguna línea? 

Se tiene la siguiente sección de la red del metro, en donde se indica la capacidad de miles de personas que se pueden transportar entre estaciones y líneas. En las horas de mayor aglomeración se registra una cantidad considerable de personas que se transportan desde Pantitlán hasta otras partes de la red como lo es Tacuba. Se sabe que a cierto hora en Pantitlan se tiene a 12 mil personas esperando ser transportadas, ¿será posible de acuerdo a la red planteada transportarlas a todas? De no ser posible, ¿cuánto es lo máximo qué podemos transportar?