Ejercicios resueltos de flujos en redes

Vértices: $\{s, A, B, C, D, t\}$

Capacidades: $c(s,A)=8, c(s,B)=10, c(A,C)=5, c(A,D)=8, c(B,C)=7, c(B,D)=3, c(C,t)=10, c(D,t)=6$

Iteración 1: Buscar camino aumentante $s \to A \to C \to t$

• Capacidad residual: $\min(8, 5, 10) = 5$
• Actualizar flujo: $f(s,A) = 5, f(A,C) = 5, f(C,t) = 5$
• Flujo total: 5

Iteración 2: Buscar camino aumentante $s \to B \to D \to t$

• Capacidad residual: $\min(10, 3, 6) = 3$
• Actualizar flujo: $f(s,B) = 3, f(B,D) = 3, f(D,t) = 3$
• Flujo total: 5 + 3 = 8

Iteración 3: Buscar camino aumentante $s \to A \to D \to t$

• Capacidades residuales: $c_r(s,A) = 8-5 = 3, c_r(A,D) = 8, c_r(D,t) = 6-3 = 3$
• Capacidad residual: $\min(3, 8, 3) = 3$
• Actualizar flujo: $f(s,A) = 8, f(A,D) = 3, f(D,t) = 6$
• Flujo total: 8 + 3 = 11

Iteración 4: Buscar camino aumentante $s \to B \to C \to t$

• Capacidades residuales: $c_r(s,B) = 10-3 = 7, c_r(B,C) = 7, c_r(C,t) = 10-5 = 5$
• Capacidad residual: $\min(7, 7, 5) = 5$
• Actualizar flujo: $f(s,B) = 8, f(B,C) = 5, f(C,t) = 10$
• Flujo total: 11 + 5 = 16

Iteración 5: Buscar caminos aumentantes

Capacidades residuales restantes:

• $c_r(s,A) = 0, c_r(s,B) = 2$
• $c_r(A,C) = 0, c_r(A,D) = 5$
• $c_r(B,C) = 2, c_r(B,D) = 0$
• $c_r(C,t) = 0, c_r(D,t) = 0$

No existe camino de $s$ a $t$ en el grafo residual.

Flujo máximo: 16

Hacer BFS desde $s$ en el grafo residual final:

• $s \to B$ (residual 2), $B \to C$ (residual 2), $C \to A$ (arista inversa, residual 5), $A \to D$ (residual 5)
• Alcanzables desde $s$: $\{s, A, B, C, D\}$
• No alcanzables: $\{t\}$

Corte mínimo: $S = \{s, A, B, C, D\}, T = \{t\}$

Aristas del corte y sus capacidades:

• $(C,t)$: capacidad 10
• $(D,t)$: capacidad 6

Capacidad del corte: $c(S,T) = 10 + 6 = 16$

• Flujo máximo encontrado: 16
• Capacidad del corte mínimo: 16
• Teorema verificado: Flujo máximo = Corte mínimo $\checkmark$

Verificación de conservación de flujo:

• En $A$: entrada 8 = salida $5 + 3$ $\checkmark$
• En $B$: entrada 8 = salida $5 + 3$ $\checkmark$
• En $C$: entrada $5 + 5 = 10$ = salida 10 $\checkmark$
• En $D$: entrada $3 + 3 = 6$ = salida 6 $\checkmark$

Problema: Dado un grafo bipartito $G = (X \cup Y, E)$, encontrar un emparejamiento de cardinalidad máxima.

Transformación a red de flujo:

1. Añadir fuente $s$ conectada a todos los vértices de $X$ con capacidad 1
2. Añadir sumidero $t$ conectado desde todos los vértices de $Y$ con capacidad 1
3. Mantener aristas originales con capacidad 1
4. El flujo máximo = cardinalidad del emparejamiento máximo

Conjunto $X: \{x_1, x_2, x_3\}$ (trabajadores)

Conjunto $Y: \{y_1, y_2, y_3\}$ (tareas)

Aristas: $\{x_1y_1, x_1y_2, x_2y_1, x_2y_3, x_3y_2, x_3y_3\}$

Interpretación: Cada trabajador puede realizar ciertas tareas.

Vértices de la red: $\{s, x_1, x_2, x_3, y_1, y_2, y_3, t\}$

Aristas y capacidades:

• De fuente: $s \to x_i$ con capacidad 1 para $i = 1{,}2{,}3$
• Originales: Las mismas aristas $x_i y_j$ con capacidad 1
• A sumidero: $y_j \to t$ con capacidad 1 para $j = 1{,}2{,}3$

Iteración 1: Camino $s \to x_1 \to y_1 \to t$

• Capacidad residual: $\min(1, 1, 1) = 1$
• Flujo: $f(s,x_1) = 1, f(x_1,y_1) = 1, f(y_1,t) = 1$
• Flujo total: 1

Iteración 2: Camino $s \to x_2 \to y_3 \to t$

• Capacidad residual: $\min(1, 1, 1) = 1$
• Flujo: $f(s,x_2) = 1, f(x_2,y_3) = 1, f(y_3,t) = 1$
• Flujo total: 2

Iteración 3: Camino $s \to x_3 \to y_2 \to t$

• Capacidad residual: $\min(1, 1, 1) = 1$
• Flujo: $f(s,x_3) = 1, f(x_3,y_2) = 1, f(y_2,t) = 1$
• Flujo total: 3

Iteración 4: Buscar más caminos

Capacidades residuales:

• $c_r(s, x_i) = 0$ para todo $i$ (fuente agotada)
• No hay más caminos aumentantes

Flujo máximo: 3

Aristas con flujo 1 en el grafo original:

• $x_1 \leftrightarrow y_1$
• $x_2 \leftrightarrow y_3$
• $x_3 \leftrightarrow y_2$

Emparejamiento máximo: $\{(x_1,y_1), (x_2,y_3), (x_3,y_2)\}$

Cardinalidad: 3 (emparejamiento perfecto)

Teorema de König: En un grafo bipartito, el tamaño del emparejamiento máximo = tamaño de la cobertura de vértices mínima.

Encontrar cobertura de vértices mínima:

Necesitamos un conjunto $S$ de vértices tal que toda arista tenga al menos un extremo en $S$.

Una cobertura: $\{x_1, x_2, x_3\}$ (cubre todas las aristas)

Tamaño: 3

Verificación: Emparejamiento máximo = 3, Cobertura mínima = 3 $\checkmark$

Modificar el grafo: Remover las aristas $x_1y_2$ y $x_3y_2$

Nuevas aristas: $\{x_1y_1, x_2y_1, x_2y_3, x_3y_3\}$

Aplicar Ford-Fulkerson:

• Camino 1: $s \to x_1 \to y_1 \to t$ (flujo 1)
• Camino 2: $s \to x_2 \to y_3 \to t$ (flujo 1)
• Camino 3: No existe camino aumentante para $x_3$ ($y_3$ está ocupado y $x_2$ no puede cambiar a $y_1$, que usa $x_1$ sin alternativa)

Emparejamiento máximo modificado: $\{(x_1,y_1), (x_2,y_3)\}$

Cardinalidad: 2

Vértice no emparejado: $y_2$ (ningún trabajador puede realizar esta tarea)

Para emparejamiento en grafos bipartitos:

• Ford-Fulkerson general: $O(VE)$ (el flujo máximo es a lo sumo $V$)
• Con BFS (Edmonds-Karp): $O(VE^2)$
• Algoritmo específico de emparejamiento (Hopcroft-Karp): $O(E\sqrt{V})$

Para el ejemplo: $V = 8, E = 12$, muy eficiente en todos los casos.

Aplicaciones prácticas:

• Asignación de tareas a trabajadores
• Emparejamiento de estudiantes con universidades
• Asignación de recursos en sistemas distribuidos

Orígenes: $O_1, O_2, O_3$ con suministros $s_1 = 100, s_2 = 150, s_3 = 120$

Destinos: $D_1, D_2, D_3$ con demandas $d_1 = 80, d_2 = 130, d_3 = 160$

Verificar balance: $\sum s_i = 370 = \sum d_j$ $\checkmark$ (problema balanceado)

Costos unitarios de transporte:

$$C = \begin{pmatrix} & D_1 & D_2 & D_3 \\ O_1 & 4 & 6 & 8 \\ O_2 & 5 & 3 & 7 \\ O_3 & 6 & 4 & 2 \end{pmatrix}$$

Vértices: $\{s, O_1, O_2, O_3, D_1, D_2, D_3, t\}$

Aristas y parámetros:

• $(s, O_i)$: capacidad $s_i$, costo 0
• $(O_i, D_j)$: capacidad $\min(s_i, d_j)$, costo $c_{ij}$
• $(D_j, t)$: capacidad $d_j$, costo 0

Demanda total en el sumidero: 370

Idea: Asignar iterativamente a las rutas con menor costo de penalización.

Iteración 1:

Calcular penalizaciones (diferencia entre dos costos mínimos por fila/columna):

Mayor penalización: Columna $D_3$ (5)

Menor costo en $D_3: O_3 \to D_3$ (costo 2)

Asignar: $x_{33} = \min(120, 160) = 120$

Iteración 2:

Actualizar tabla ($O_3$ agotado, $D_3$ necesita 40 más):

Mayor penalización: Columna $D_2$ (3)

Asignar: $x_{22} = \min(150, 130) = 130$

Iteración 3:

Actualizar ($O_2$ tiene 20 restante, $D_2$ satisfecho):

Asignar: $x_{23} = 20, x_{13} = 20, x_{11} = 80$

Costo total inicial: $320 + 160 + 390 + 140 + 240 = 1250$

Variables duales: $u_i$ (orígenes), $v_j$ (destinos)

Condición: $u_i + v_j = c_{ij}$ para variables básicas

Sistema de ecuaciones:

• $u_1 + v_1 = 4$ (de $x_{11} = 80$)
• $u_1 + v_3 = 8$ (de $x_{13} = 20$)
• $u_2 + v_2 = 3$ (de $x_{22} = 130$)
• $u_2 + v_3 = 7$ (de $x_{23} = 20$)
• $u_3 + v_3 = 2$ (de $x_{33} = 120$)

Resolver: Fijar $u_1 = 0$

• $v_1 = 4, v_3 = 8$
• $u_2 = 7 - 8 = -1$
• $v_2 = 3 - (-1) = 4$
• $u_3 = 2 - 8 = -6$

Para variables no básicas: $\bar{c}_{ij} = c_{ij} - u_i - v_j$

• $\bar{c}_{12} = 6 - 0 - 4 = 2 > 0$
• $\bar{c}_{21} = 5 - (-1) - 4 = 2 > 0$
• $\bar{c}_{31} = 6 - (-6) - 4 = 8 > 0$
• $\bar{c}_{32} = 4 - (-6) - 4 = 6 > 0$

Todos los costos reducidos son no negativos → Solución óptima encontrada

Flujos óptimos:

• $O_1 \to D_1$: 80 unidades
• $O_1 \to D_3$: 20 unidades
• $O_2 \to D_2$: 130 unidades
• $O_2 \to D_3$: 20 unidades
• $O_3 \to D_3$: 120 unidades

Costo mínimo total: 1250

Verificación de restricciones:

• Suministros: $O_1(100)$, $O_2(150)$, $O_3(120)$ $\checkmark$
• Demandas: $D_1(80)$, $D_2(130)$, $D_3(160)$ $\checkmark$
• Balance: $370 = 370$ $\checkmark$

Idea: Encontrar repetidamente caminos aumentantes hasta que no existan más.

Complejidad en el peor caso:

• Con capacidades enteras: $O(E \cdot f^*)$ donde $f^*$ es el flujo máximo
• Con capacidades racionales: Puede no terminar con búsqueda arbitraria de caminos
• Dependencia del valor: La complejidad depende de $f^*$, no solo del tamaño del grafo

Ejemplo patológico:

Red con capacidades grandes pero caminos aumentantes de capacidad 1:

• Fuente $s \to A(1000), s \to B(1000)$
• $A \to B(1), B \to A(1)$
• $A \to t(1000), B \to t(1000)$

Si elegimos alternativamente caminos $s \to A \to B \to t$ y $s \to B \to A \to t$:

• Cada iteración aumenta flujo en 1
• Necesitamos 2000 iteraciones para flujo máximo 2000
• Complejidad: $O(E \cdot f^*) = O(6 \cdot 2000) = O(12000)$

Mejora: Usar BFS para encontrar caminos aumentantes (caminos más cortos).

Complejidad: $O(VE^2)$

• Independiente del valor: Solo depende del tamaño del grafo
• Cota en el número de iteraciones: A lo sumo $O(VE)$ iteraciones
• Costo por iteración: $O(E)$ para BFS

Análisis teórico:

• La distancia mínima de $s$ a $t$ es no decreciente
• Cuando una arista $(u,v)$ se satura, la distancia $d(u)$ aumenta
• Cada arista puede saturarse a lo sumo $O(V)$ veces

Paradigma diferente: Mantener un "preflow" y ajustar alturas de vértices.

Conceptos clave:

• Preflow: $f(u,v) \geq 0$, $\sum f(v,u) \geq \sum f(u,v)$ para $u \neq s,t$
• Altura: $h(u)$ = estimación de distancia a $t$
• Exceso: $ex(u) = \sum f(v,u) - \sum f(u,v)$

Operaciones:

1. Push: Enviar exceso de $u$ a $v$ si $h(u) = h(v) + 1$
2. Relabel: Aumentar $h(u)$ si $ex(u) > 0$ y no se puede hacer push

Complejidades de Push-Relabel:

• Versión básica: $O(V^2 E)$
• Con heurística FIFO: $O(V^3)$
• Con heurística "highest-label": $O(V^2 \sqrt{E})$

Red tipo 1: Grafo denso ($V = 100, E = 5000$)

Red tipo 2: Grafo disperso ($V = 1000, E = 2000$)

Red tipo 3: Capacidades unitarias ($V = 500, E = 1500$)

Redes bipartitas (emparejamiento):

• Hopcroft-Karp: $O(E\sqrt{V})$ específico para emparejamiento
• Edmonds-Karp aplicado: $O(VE^2)$ genérico
• Ventaja especializada: Factor $\sqrt{V}$ de mejora

Redes planares:

• Algoritmos especializados: $O(V \log V)$ para redes planares
• Push-relabel planar: $O(V \log V)$ usando propiedades geométricas

Redes con capacidades grandes:

• Ford-Fulkerson: Muy malo, $O(E \cdot f^*)$
• Scaling algorithms: $O(E^2 \log C)$ donde $C$ es la capacidad máxima
• Push-relabel: No afectado por valores de capacidades

Usar Ford-Fulkerson cuando:

• Capacidades pequeñas y enteras
• Red simple y pequeña
• Implementación debe ser mínima

Usar Edmonds-Karp cuando:

• Se necesita garantía de terminación
• Red de tamaño medio ($V, E \leq 10^4$)
• Balance entre simplicidad y rendimiento

Usar Push-Relabel cuando:

• Redes muy densas ($E \approx V^2$)
• Redes grandes ($V > 10^4$)
• Se dispone de implementación optimizada

Usar algoritmos especializados cuando:

• Problema específico (emparejamiento, redes planares)
• Rendimiento crítico
• Estructura particular explotable

Factores que afectan el rendimiento práctico:

1. Representación del grafo: Lista vs matriz de adyacencia
2. Estructuras de datos: Colas, heaps para diferentes algoritmos
3. Heurísticas: Gap heuristic en push-relabel, shortest path heuristic
4. Paralelización: Push-relabel se paraléliza mejor que Ford-Fulkerson

Complejidad de espacio:

• Todos los algoritmos: $O(V + E)$ para almacenar el grafo
• Push-relabel: $O(V)$ adicional para alturas y excesos
• Trade-off: Tiempo vs espacio según la aplicación