Irreducibilidad

01 · Punto de partida

Un mundo o varios

Dos grupos sin puente son dos mundos: lo que empieza a la izquierda muere a la izquierda. Con un puente (aunque chico) vuelven a ser un mundo: todo llega a todo.

Esa es la irreducibilidad: todos los estados se comunican. Cierra el bloque de clasificación y abre tiempos y equilibrio.

• ¿Desde i se llega a j por algún camino?
• ¿Y de vuelta de j a i?
• ¿Hay un puente cuya chance 0 parte el mundo?
• ¿El destino final depende del inicio?

02 · Definición

¿Qué es irreducible?

Una sola condición exigente:

En finitas, irreducible ⇒ todos recurrentes (un mundo cerrado). El destino a largo plazo no depende del inicio (salvo período).

03 · Anatomía

Puente, corte y herencia

Cuatro reglas para dictaminar:

Puente > 0

Una sola flecha ida y otra vuelta (o un camino) bastan para unir. La cantidad no importa, la existencia sí.

Corte en 0

Si el puente vale 0, el mundo se parte. Un parámetro en cero cambia la topología.

Herencia

En irreducibles finitas: recurrencia, período y π unica se comparten.

Destino único

Con una sola cerrada, el largo plazo no depende de X₀ (aperiódica mediante).

04 · Ejemplos

Mundos que se unen o se parten

Buscá el puente: si existe en ambas direcciones, hay un mundo.

1. 1
   Anillo con lazos.

   Irreducible: todo conecta por el anillo.

2. 2
   Dos equipos sin pases.

   Reducible: cada equipo es un mundo cerrado.

3. 3
   Fuga + trampa.

   Reducible: abierta → cerrada sin vuelta.

4. 4
   Puente chico b = 0,01.

   Irreducible igual: tarda, pero llega.

5. 5
   Cola 0…K.

   Irreducible en su rango: escalera conectada con bordes.

05 · Representación en Python

Todos con todos por BFS

En Python, irreducible se verifica con alcanzabilidad mutua: desde cada i se llega a cada j. Un solo par sin vuelta y es reducible.

def alcanzables(g, i):
    vistos, pila = set(), [i]
    while pila:
        x = pila.pop()
        if x in vistos:
            continue
        vistos.add(x)
        pila.extend(g.get(x, []))
    return vistos

def irreducible(g):
    nodos = list(g)
    return all(j in alcanzables(g, i) for i in nodos for j in nodos)

anillo = {0: [0, 1, 3], 1: [0, 1, 2], 2: [1, 2, 3], 3: [2, 3, 0]}
print("anillo:", irreducible(anillo))

El anillo da True: 4 nodos, un mundo. Cada par tiene ida y vuelta por el aro.

Cortar el puente

Sin las flechas 1↔2 quedan dos mundos:

def alcanzables(g, i):
    vistos, pila = set(), [i]
    while pila:
        x = pila.pop()
        if x in vistos:
            continue
        vistos.add(x)
        pila.extend(g.get(x, []))
    return vistos

def irreducible(g):
    nodos = list(g)
    return all(j in alcanzables(g, i) for i in nodos for j in nodos)

corte = {0: [0, 1], 1: [0, 1], 2: [2, 3], 3: [2, 3]}
print("corte:", irreducible(corte))
print("0->2:", 2 in alcanzables(corte, 0))

06 · Exploración

Laboratorio: el puente une mundos

Izquierda {0, 1} y derecha {2, 3} con puente b = P(1→2) = P(2→1). Con b = 0 son dos mundos (colores separados, destinos propios); con b > 0 el puente verde los une en uno. Simulamos 200 pasos desde 0 y desde 3.

El grosor verde del puente marca b. Las barras laterales muestran cruces en 200 pasos: con b = 0 son cero.

Preguntas para explorar

1. Con b = 0, ¿desde 0 se llega a la derecha en 200 pasos? ¿Y al revés?
2. Subí b a 0,05. ¿Ya hay cruces? ¿Cuántas clases quedan?
3. ¿Un puente de un solo sentido (1→2 sin vuelta) une o no?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: diagnosticar un mundo

¿Esta cadena 3×3 en anillo es irreducible? Verificá todos con todos.

def alcanzables(g, i):
    vistos, pila = set(), [i]
    while pila:
        x = pila.pop()
        if x in vistos:
            continue
        vistos.add(x)
        pila.extend(g.get(x, []))
    return vistos

g = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
print(all(j in alcanzables(g, i) for i in g for j in g))

Ejercicio 2: partir con un cero

Sin ejecutar primero: al quitar 1→2 y 2→1 del anillo 0–1–2–3, ¿sigue irreducible? Comprobalo.

def alcanzables(g, i):
    vistos, pila = set(), [i]
    while pila:
        x = pila.pop()
        if x in vistos:
            continue
        vistos.add(x)
        pila.extend(g.get(x, []))
    return vistos

g = {0: [0, 1, 3], 1: [0, 1], 2: [2, 3], 3: [2, 3, 0]}
nodos = list(g)
print(all(j in alcanzables(g, i) for i in nodos for j in nodos))
print("0->2:", 2 in alcanzables(g, 0))

Ejercicio 3: puente mínimo

¿Qué par de flechas une {0,1} con {2,3} en un mundo? Escribí el grafo mínimo.

g = {0: [1], 1: [0, 2], 2: [3, 1], 3: [2]}
print("puente: 1->2 y 2->1")

09 · Síntesis

Ideas para recordar

Cerramos clasificación. En el próximo bloque mediremos tiempos: alcance y absorción.