Calculadora de Flujo de Red (Flujo Máximo)

Calculadora de Flujo de Red (Flujo Máximo)

La Calculadora de Flujo de Red Flujo Máximo calcula el flujo máximo desde una fuente elegida s hasta un sumidero elegido t en cualquier red dirigida con capacidades. Internamente ejecuta el método de Ford-Fulkerson con rutas de aumento mediante búsqueda en anchura (el algoritmo de Edmonds-Karp), y registra cada ruta encontrada para que puedas repasar todo el proceso de decisión iteración tras iteración. La página de resultados también revela el corte mínimo, la partición de cuello de botella que demuestra que el valor de flujo obtenido es verdaderamente óptimo.

¿Qué es el problema del flujo máximo?

Una red de flujo es un grafo dirigido G = (V, E) junto con una función de capacidad c: E → ℝ_≥0. Se distinguen dos vértices: la fuente s (donde se origina el flujo) y el sumidero t (donde se consume). Un flujo f es cualquier asignación f(u, v) ≥ 0 en las aristas que cumple:

El problema del flujo máximo consiste en encontrar el flujo f que maximiza |f|. Intuitivamente: si las aristas fueran tuberías de agua con las capacidades dadas, ¿cuántos litros por segundo puedes enviar de s a t?

Cómo funciona el algoritmo — Ford-Fulkerson con BFS

El algoritmo mantiene un grafo residual junto con el flujo actual. Para cada arista (u, v) con capacidad c y flujo actual f, el grafo residual contiene:

• una arista residual directa (u, v) con capacidad c − f (cuánto más se puede empujar), y
• una arista residual inversa (v, u) con capacidad f (cuánto del flujo ya asignado se puede cancelar).

En cada iteración, realiza una búsqueda en anchura (BFS) de s a t sobre el grafo residual. Si se encuentra una ruta, la menor capacidad de arista en la ruta —el cuello de botella— se suma al flujo de cada arista directa y se resta de cada arista inversa a lo largo de la ruta. Esto se llama una ruta de aumento. Cuando la BFS ya no puede llegar a t, el flujo actual es óptimo.

Usar BFS (en lugar de una búsqueda de rutas arbitraria) convierte a Ford-Fulkerson en Edmonds-Karp, con un tiempo de ejecución garantizado de O(V · E²). También garantiza la terminación con capacidades irracionales, algo que el Ford-Fulkerson estándar no logra.

El teorema de flujo máximo y corte mínimo

Un corte es una partición de los vértices en dos conjuntos (S, T) con s ∈ S y t ∈ T. Su capacidad es la suma de las capacidades de las aristas que van de S a T:

El teorema de flujo máximo y corte mínimo (Ford y Fulkerson, 1956) establece:

Esta herramienta encuentra el corte mínimo automáticamente. Una vez que Edmonds-Karp termina, ejecuta una BFS final desde s en el grafo residual; los vértices alcanzados forman S, el resto forman T, y cada arista que cruza de S → T en el grafo original está saturada. La suma de sus capacidades es exactamente el valor del flujo máximo — visible en el resultado principal como "Capacidad del corte mínimo ✓ confirma optimalidad".

Características diseñadas para el aprendizaje

• Animación paso a paso. Reproduce cada ruta de aumento con controles de reproducción, pausa y pasos. Observa qué ruta eligió la BFS, qué arista fue el cuello de botella y cómo creció el total acumulado.
• Tres matrices sincronizadas. Alterna entre la matriz de capacidad C, la matriz de flujo final f y la matriz residual C − f — las tres imágenes que juntas caracterizan cualquier flujo.
• Vista de partición de corte mínimo. Los vértices de los lados S y T se listan como fichas con las aristas saturadas que los cruzan resaltadas en rojo.
• Tabla arista por arista. Para cada arista: capacidad, flujo, residual, barra de utilización y un indicador de saturación.
• Diseño en capas de izquierda a derecha. El dibujo del grafo se calcula a partir de las distancias BFS desde la fuente, de modo que el flujo "corre" visiblemente de izquierda a derecha, tal como lo dibujan los libros de texto.

Formatos de entrada

1. Lista de aristas con capacidades

Una arista por línea. La forma con flecha es la más legible, pero funcionan varias alternativas:

También se acepta: A, B, 10 · A B 10 · A -> B , 10. Las aristas múltiples entre el mismo par de nodos se suman.

2. Matriz de capacidad

Una fila por línea, valores separados por espacios o comas. La entrada C[i][j] es la capacidad de la arista del vértice i al vértice j. Usa 0 para "sin arista". La matriz debe ser cuadrada y la diagonal debe ser 0 (sin bucles sobre sí mismo).

Introduce las etiquetas de vértices correspondientes en el campo Etiquetas de matriz (separadas por comas o espacios). Si se omite, las etiquetas por defecto serán S, A, B, …, T.

Aplicaciones del flujo máximo

Ejemplo resuelto

El ejemplo rápido "Libro de texto" codifica una red de 6 nodos con fuente S y sumidero T. Ejecutar Edmonds-Karp produce cuatro rutas de aumento:

1. S → A → B → T con cuello de botella 4 (la arista A-B es la limitante). Total acumulado: 4.
2. S → A → D → T con cuello de botella 6. Total acumulado: 10.
3. S → C → D → T con cuello de botella 4 (la arista D-T es ahora la limitante, solo quedan 4). Total acumulado: 14.
4. S → C → D → B → T con cuello de botella 5. Total acumulado: 19.

El algoritmo se detiene; ya no existen más rutas de aumento. El corte mínimo es (S = {S, C}, T = {A, B, D, T}) con las aristas cruzadas S → A (capacidad 10) y C → D (capacidad 9), que suman 19 — exactamente el valor del flujo máximo.

Cómo usar esta calculadora

1. Elige el formato de entrada usando las pestañas — lista de aristas (recomendado) o matriz de capacidad.
2. Introduce tu red. Puedes empezar desde un ejemplo rápido y modificarlo. Para la entrada de matriz, suministra también las etiquetas si quieres nombres distintos a S, A, B, …, T.
3. Especifica fuente y sumidero (o déjalos en blanco para detectar automáticamente S y T).
4. Haz clic en Calcular Flujo Máximo. La página de resultados muestra el valor de flujo máximo, la partición de corte mínimo, una visualización del grafo en capas, cada ruta de aumento, una tabla de utilización de aristas y tres matrices (capacidad, flujo, residual).
5. Reproduce la animación debajo del grafo para revisar las decisiones del algoritmo. Haz clic en cualquier paso de ruta de aumento para saltar directamente a él.

Límites

• Vértices: hasta 30 — mantiene legibles la visualización y las matrices.
• Aristas: hasta 200.
• Capacidades: no negativas, hasta 10⁹. Se permiten capacidades fraccionarias.
• Sin bucles sobre sí mismo: Los bucles sobre el mismo nodo no transportan flujo en una formulación estándar de flujo máximo y son rechazados.

Preguntas frecuentes

¿Qué es el problema del flujo máximo?

Dada una red dirigida donde cada arista tiene una capacidad no negativa, el problema del flujo máximo pregunta: ¿cuánto flujo se puede enviar desde un vértice fuente designado s hasta un vértice sumidero designado t, sujeto a las reglas de que el flujo en cada arista no puede exceder su capacidad y el flujo que entra en cada vértice que no sea fuente ni sumidero debe ser igual al flujo que sale de él? El resultado se llama valor de flujo máximo.

¿Qué es el método de Ford-Fulkerson?

Ford-Fulkerson es una técnica general para calcular el flujo máximo. Encuentra repetidamente una ruta de aumento desde la fuente al sumidero en el grafo residual y empuja tanto flujo como sea posible a lo largo de esa ruta (la capacidad del cuello de botella), luego actualiza el grafo residual. El procedimiento termina cuando no existe ninguna ruta de aumento. Cuando se implementa con búsqueda en anchura (BFS) para la selección de rutas, se llama Edmonds-Karp y se ejecuta en tiempo O(V · E²).

¿Qué es el corte mínimo de una red de flujo?

Un corte es una partición de los vértices en dos conjuntos S y T tales que la fuente está en S y el sumidero está en T. La capacidad del corte es la suma de las capacidades de las aristas de S a T. Un corte mínimo es un corte de capacidad mínima. El famoso teorema de flujo máximo y corte mínimo demuestra que el valor del flujo máximo siempre es igual a la capacidad del corte mínimo.

¿Qué es el grafo residual?

El grafo residual rastrea cuánto flujo adicional se puede empujar todavía en cada arista. Para cada arista original (u, v) con capacidad c y flujo actual f, el grafo residual contiene una arista hacia adelante (u, v) con capacidad c menos f (capacidad restante) y una arista inversa (v, u) con capacidad f (flujo cancelable). Una ruta de aumento utiliza aristas del grafo residual, lo que permite al algoritmo deshacer decisiones anteriores.

¿Por qué la herramienta usa BFS para las rutas de aumento?

Elegir rutas de aumento con búsqueda en anchura (Edmonds-Karp) garantiza la terminación en tiempo polinomial independientemente de las capacidades de las aristas. El Ford-Fulkerson simple con una estrategia arbitraria de búsqueda de rutas puede entrar en un bucle de un número exponencial de iteraciones en entradas patológicas, y con capacidades irracionales puede no terminar nunca. BFS también produce las rutas de aumento más cortas, que son más fáciles de leer y analizar.

¿Qué significa una arista saturada?

Una arista está saturada cuando su flujo es igual a su capacidad, por lo que no se puede empujar flujo adicional a través de ella. Las aristas saturadas son los cuellos de botella de la red, y cada corte mínimo consiste enteramente en aristas saturadas desde el lado S al lado T del corte. La herramienta resalta las aristas saturadas en rojo para que puedas ver la estructura del cuello de botella de un vistazo.

Lectura adicional

• Problema del flujo máximo — Wikipedia
• Algoritmo de Ford–Fulkerson — Wikipedia
• Algoritmo de Edmonds–Karp — Wikipedia
• Teorema de flujo máximo y corte mínimo — Wikipedia