← Volver a los ejercicios

La fibra de un campus

El último y el más exigente, para cuando los anteriores ya salen solos. Quince edificios y veinte enlaces de fibra: demasiado para trazar la búsqueda de memoria, que es el tamaño en que estos algoritmos dejan de ser un ejercicio de papel. Un edificio o un enlace es un punto único de falla cuando, al quedar fuera de servicio, la red se parte en pedazos que ya no se ven entre sí.

1. La red

Cada nodo y cada enlace de las listas de abajo trae un botón que lo quita del dibujo y vuelve a colorear lo que queda. Un enlace de prueba, si se agrega más abajo, se dibuja punteado y no entra en los botones de quitar.

2. Marque a mano los puntos únicos de falla

Entrada: la red de fibra.  Salida: los edificios cuya caída parte la red, y los enlaces cuya caída hace lo mismo. Pruebe con los botones de quitar y marque sus respuestas antes de pasar al siguiente paso.

Edificios

Enlaces

3. Corra cortes y compare

EdificiodlowPadre en el árbolMarca

Después de correr, los puntos de articulación quedan con borde rojo en el dibujo y los puentes en rojo grueso.

4. Reforzar la red con un enlace

Escoja dos edificios que no estén unidos y agregue un enlace de prueba. cortes corre de nuevo sobre la red con el enlace y dice cuántos puntos únicos de falla quedan.

con

5. Para llevarse

Sin solución aquí. Tres preguntas sobre la misma red.