La Anomalía en la Matrix

Se dice que Smith es “la anomalía”: el resultado inevitable de un sistema que, tarde o temprano, empieza a copiarse a sí mismo sin pedir permiso. Zion lo sabe, y por eso antes de actuar necesita entender la red en la que se mueve. Qué tan lejos puede llegar una amenaza, si hay caminos de vuelta, si conviene revisar cada rincón una sola vez o si un reinicio puede completarse sin trabarse en sí mismo. Este sendero recorre cuatro problemas distintos sobre la misma pregunta de fondo: ¿qué se puede saber de una red, sin recorrerla entera a ciegas, antes de decidir qué hacer con ella?

Vas a seguir la propagación de Smith apenas consigue su primer host, vas a acompañar a un equipo que busca una salida por los túneles de mantenimiento de Zion, vas a caminar con Seraph una ronda que no admite un solo paso de más, y vas a terminar reiniciando el núcleo de Zion pieza por pieza, con la certeza de que un solo error de dependencia puede dejarlo todo trabado para siempre.

---

La Multiplicación del Agente

Dificultad: ★☆☆☆☆

Smith consiguió instalarse en un host cualquiera de la red del Matrix (le dicen “Terminal Cero”) y desde ahí empezó a replicarse, salto a salto, hacia cualquier host directamente conectado. Zion no puede desconectar toda la red a la vez, así que necesita algo más preciso: saber, ronda por ronda, qué hosts van a caer y, sobre todo, cuántas rondas le quedan antes de que Smith llegue a un punto que no se pueden dar el lujo de perder.

Enunciado

Se modela la red como un grafo no dirigido $G=(V,E)$, donde cada host es un vértice y cada conexión directa entre dos hosts es una arista. Smith se replica de a un salto por ronda: en la ronda 0 solo controla el host inicial; en cada ronda siguiente, controla además todo host conectado directamente a alguno que ya controlaba.

1. Justificar qué estructura de datos conviene usar para representar esta red, sabiendo que el Matrix tiene muchísimos hosts pero cada uno con relativamente pocas conexiones directas (un grafo disperso). Comparar explícitamente lista de adyacencia contra matriz de adyacencia para este caso.
2. Diseñar el algoritmo que, a partir del host inicial, determine en qué ronda cae cada host de la red.
3. Trazar el algoritmo a mano sobre la siguiente red, empezando en “Terminal Cero”:

Extremo 1	Extremo 2
Terminal Cero	Backdoor de Woo
Terminal Cero	Relé de Sati
Backdoor de Woo	Consola del Oráculo
Backdoor de Woo	Nodo del Merovingio
Relé de Sati	Nodo del Merovingio
Relé de Sati	Enlace del Trainman
Nodo del Merovingio	Servidor del Arquitecto
Enlace del Trainman	Servidor del Arquitecto
Servidor del Arquitecto	La Puerta de Sion

Además de esta lista, existe un host llamado “Búnker Aislado” que no tiene ninguna conexión con el resto de la red. Indicar en qué ronda cae cada host, cuántas rondas tarda Smith en llegar a “La Puerta de Sion”, y qué ocurre con el “Búnker Aislado”.

4. Determinar la complejidad del algoritmo en función de $V$ y $E$, y explicar cómo cambiaría si se hubiese elegido, en el punto 1, la representación menos conveniente para este tipo de red.

Abrir artículo

---

Los Túneles de Zion

Dificultad: ★★☆☆☆

Con Smith avanzando, un equipo necesita evacuar por los túneles de mantenimiento de Zion, una red de pasadizos angostos, mal iluminados, algunos de los cuales vuelven sobre sí mismos sin llevar a ninguna parte. Antes de arriesgarse a entrar, el equipo quiere dos cosas: un mapa de por dónde se puede salir sin dar vueltas en círculo, y la certeza de que no hay ningún sector del refugio completamente incomunicado del resto.

Enunciado

La red de túneles es un grafo no dirigido $G=(V,E)$, donde cada vértice es un cruce o punto de interés y cada arista es un pasadizo transitable en ambos sentidos.

1. Explicar qué información, obtenida durante un DFS, permite determinar si el grafo tiene algún ciclo (relacionarlo con el concepto de arista de retroceso visto en clase) y qué determina si dos nodos pertenecen a la misma componente conexa.
2. Diseñar el algoritmo que recorra la red completa y devuelva: el árbol de recorrido, si existe al menos un ciclo, y la cantidad total de componentes conexas.
3. Trazar el DFS a mano empezando en “Entrada”, mostrando el estado de la pila (o de las llamadas recursivas) y el array de visitados en cada paso, sobre la siguiente red:

Extremo 1	Extremo 2
Entrada	Cruce 1
Entrada	Cruce 2
Cruce 1	Cruce 3
Cruce 2	Cruce 3
Cruce 3	Cruce 4
Cruce 4	Cruce 5
Cruce 5	Refugio
Cruce 2	Cruce 5
Pasadizo Olvidado 1	Pasadizo Olvidado 2
Pasadizo Olvidado 2	Pasadizo Olvidado 3

4. A partir de la traza: indicar cuántas componentes conexas tiene la red, si existe algún ciclo (y cuál es, en caso de que lo haya), y la complejidad del algoritmo en función de $V$ y $E$.

Abrir artículo

---

La Ronda de Seraph

Dificultad: ★★★☆☆

Seraph custodia el acceso a la mansión del Merovingio, y antes de que Zion se anime a pedirle un favor necesita confirmar algo: que puede recorrer cada pasillo de la mansión exactamente una vez, sin dejar ninguno sin revisar y sin pasar dos veces por el mismo. Volver a cruzar un pasillo ya recorrido es, para cualquiera que esté mirando, la señal más clara de que alguien está buscando algo.

Enunciado

El plano de la mansión es un grafo no dirigido $G=(V,E)$, donde cada vértice es una habitación y cada arista es un pasillo que la conecta con otra.

1. Explicar el criterio (teorema de Euler) que determina, a partir del grado de los vértices, si un grafo tiene un circuito euleriano, un camino euleriano, o ninguno de los dos. Justificar por qué la cantidad de vértices de grado impar tiene que ser exactamente $0$ o exactamente $2$ para que exista alguna de las dos rutas, y no otro número.
2. Aplicar el criterio al siguiente plano y determinar si la ronda de Seraph es posible. En caso de que lo sea, indicar si se trata de un circuito o de un camino euleriano, y en qué habitación conviene empezar (y, si corresponde, en cuál termina necesariamente):

Extremo 1	Extremo 2
Entrada	Vestíbulo
Vestíbulo	Salón
Salón	Biblioteca
Biblioteca	Comedor
Comedor	Bodega
Bodega	Oficina del Merovingio
Oficina del Merovingio	Entrada
Vestíbulo	Comedor

3. Construir a mano una ronda válida: la secuencia completa de habitaciones que recorre cada pasillo exactamente una vez.
4. Determinar la complejidad de verificar la condición de Euler (contar los grados de todos los vértices) en función de $V$ y $E$. Explicar además por qué saber que la ronda existe no alcanza por sí solo para construirla: ¿qué información adicional hubo que usar en el punto 3 que no se necesitó en el punto 2?

---

Ver solución

1. El criterio de Euler

Un circuito o camino euleriano recorre cada arista exactamente una vez. La clave para saber si existe está en contar, para cada vértice, cuántas veces se lo “usa de paso”:

• Cada vez que la ronda pasa por un vértice (sin quedarse), entra por una arista y sale por otra: consume las aristas de ese vértice de a pares.
• Solo el vértice donde empieza la ronda puede tener una arista de salida sin una de entrada que la empareje, y solo el vértice donde termina puede tener una arista de entrada sin salida.

De ahí sale el criterio:

• Si $\mathrm{deg}(v)$ es par en todos los vértices $\Rightarrow$ existe un circuito euleriano (se puede empezar y terminar en el mismo lugar).
• Si exactamente dos vértices tienen grado impar $\Rightarrow$ existe un camino euleriano, y esos dos vértices son, necesariamente, el inicio y el fin.
• Si hay más de dos vértices de grado impar $\Rightarrow$ no existe ninguna de las dos rutas: no puede haber más de un vértice con una salida “sin pareja” y más de un vértice con una entrada “sin pareja” en una única ronda.

Importante: También hace falta que el grafo sea conexo, o al menos que todas las aristas estén en una sola componente, porque si no ninguna ronda que arranca de un solo lugar puede llegar a recorrerlas todas.

2. Aplicación al plano de la mansión

Habitación	Aristas incidentes	$\mathrm{deg}(v)$
Entrada	Vestíbulo, Oficina del Merovingio	2
Vestíbulo	Entrada, Salón, Comedor	3
Salón	Vestíbulo, Biblioteca	2
Biblioteca	Salón, Comedor	2
Comedor	Biblioteca, Bodega, Vestíbulo	3
Bodega	Comedor, Oficina del Merovingio	2
Oficina del Merovingio	Bodega, Entrada	2

Exactamente dos vértices de grado impar: Vestíbulo y Comedor. Por el criterio del punto 1, la ronda de Seraph es posible, pero como camino euleriano (no como circuito): tiene que empezar en una de esas dos habitaciones y terminar necesariamente en la otra.

3. Una ronda válida

Empezando en Vestíbulo y terminando en Comedor:

$\text{Vestıˊbulo}\to \text{Entrada}\to \text{Oficina del Merovingio}\to \text{Bodega}\to \text{Comedor}\to \text{Biblioteca}\to \text{Saloˊn}\to \text{Vestıˊbulo}\to \text{Comedor}$

Paso	Pasillo usado
1	Vestíbulo–Entrada
2	Entrada–Oficina del Merovingio
3	Oficina del Merovingio–Bodega
4	Bodega–Comedor
5	Comedor–Biblioteca
6	Biblioteca–Salón
7	Salón–Vestíbulo
8	Vestíbulo–Comedor

Las 8 aristas aparecen una sola vez cada una, así que la ronda es válida. No es la única ronda posible: cualquier otro orden que respete “cada arista una sola vez” y arranque en Vestíbulo o Comedor también sirve.

Notar que Seraph pasa dos veces por el Vestíbulo. Eso está permitido, lo único que no se puede repetir es el pasillo, no la habitación.

4. Complejidad, y qué falta para poder construirla

Contar el grado de cada vértice recorriendo una vez la lista de adyacencia cuesta $O(V+E)$: se visita cada vértice una vez y cada arista aporta a dos grados, así que el trabajo total es proporcional a $V+E$.

Pero ese chequeo solo mira información local (el grado de cada vértice, uno por uno). Alcanza para saber que la ronda existe, aunque no dice en qué orden recorrerla. Para construirla (punto 3) hubo que tener en cuenta algo más global: qué aristas ya se usaron y si, al elegir una arista para avanzar, no se deja “aislado” del resto un tramo todavía sin recorrer. Formalizar esa idea es exactamente lo que hacen los algoritmos de construcción de rutas eulerianas (Fleury, o el más eficiente, el de Hierholzer), fuera del alcance de este ejercicio, pero un buen próximo paso si querés ir más allá de trazarla a mano.

Abrir artículo

---

El Reinicio del Núcleo

Dificultad: ★★★★★

Con la amenaza contenida, Zion necesita reiniciar los sistemas de su propio núcleo (energía, refrigeración, soporte vital, sensores, comunicaciones, defensa) y ninguno puede encenderse antes que aquellos de los que depende. El operador a cargo tiene el mapa de dependencias entre subsistemas, pero sabe que un solo error de configuración, una sola dependencia mal puesta, puede dejar el reinicio completo esperando a sí mismo para siempre.

Enunciado

El mapa de dependencias es un grafo dirigido $G=(V,E)$, donde cada vértice es un subsistema y una arista $(v,w)$ significa que $v$ tiene que estar activo antes de que $w$ pueda iniciarse.

1. Explicar por qué el orden topológico solo está definido cuando el grafo es un DAG (grafo dirigido acíclico), y qué relación tiene esto con la detección de ciclos mediante DFS.
2. Diseñar el algoritmo (a partir del DFS recursivo y su postorden) que determine un orden válido de inicialización de los subsistemas.
3. Dado el siguiente mapa de dependencias, obtener un orden topológico válido para el reinicio (puede existir más de uno; alcanza con dar uno):

Antes	Después
Energía	Refrigeración
Energía	Soporte Vital
Refrigeración	Núcleo Central
Soporte Vital	Comunicaciones
Núcleo Central	Sensores
Núcleo Central	Defensa
Sensores	Enlace con el Oráculo
Defensa	Enlace con el Oráculo

4. Un técnico agregó, por error, una dependencia adicional: “Comunicaciones” debe confirmar el estado de “Energía” antes de que este último pueda reiniciarse. Determinar si el reinicio sigue siendo posible con esta nueva dependencia y, si no lo es, identificar exactamente el ciclo que lo impide.

Abrir artículo

---

Si este sendero te dejó pensando en cuánto se puede llegar a saber de una red sin perderse en ella: DFS y BFS son apenas la puerta de entrada. La misma idea de “explorar sistemáticamente” es la base de Dijkstra (BFS, pero con pasillos que no cuestan todos lo mismo) y de Kruskal y Prim (para conectar toda una red gastando lo menos posible). En todos los casos el desafío nunca es mirar el grafo entero de una sola vez: es encontrar la forma correcta de recorrerlo, un paso genuino por vez.