Descubriendo el Teorema de Flujo Máximo Corte Mínimo Un Enfoque Integral y Formal

Descubriendo el teorema de flujo máximo corte mínimo un enfoque integral y formal.

Explorando el campo de las redes de flujo y el teorema de flujo máximo-mínimo

Introducción

En el dominio de la optimización del flujo de redes, el teorema de flujo máximo-mínimo se destaca como un hito matemático notable. Su elegancia es la clave para resolver problemas de optimización complejos que conciernen al flujo de fluidos o recursos a través de redes compuestas por nodos interconectados por aristas. Sus aplicaciones incluyen una amplia gama de sistemas, desde redes de transporte hasta infraestructura de comunicaciones, donde la gestión eficiente del flujo es esencial. Al comprender este teorema y los conceptos fundamentales detrás de su articulación matemática, puedes desentrañar los enigmas para maximizar la utilización de recursos y alcanzar un rendimiento óptimo en una variedad de escenarios prácticos.

En este artículo, nuestro objetivo es simplificar y hacer que el teorema sea accesible para todos los lectores. Te guiaremos a través de su desarrollo histórico, delineando sus raíces desde formulaciones tempranas que nos permitirán apreciar las contribuciones de mentes prominentes que allanaron el camino para este teorema y todo su campo de estudio matemático. Además, profundizaremos en las aplicaciones del mundo real del teorema de flujo máximo-mínimo. Desde el diseño de sistemas de transporte eficientes hasta la resolución de tareas de procesamiento de imágenes, su versatilidad parece ilimitada. Al explorar sus implicaciones prácticas, presenciarás el impacto profundo del teorema en diversos campos e industrias.

Por último, el objetivo es proporcionarte una explicación completa que combine la simplicidad y la formalidad. No se requiere experiencia previa en matemáticas avanzadas, aunque algún conocimiento de teoría de grafos y matemáticas discretas (lógica y teoría de conjuntos) puede ayudar significativamente; todo lo que necesitas es una mente curiosa y la voluntad de desentrañar la utilidad de este teorema excepcional.

Historia

El teorema de flujo máximo-mínimo fue presentado por primera vez por Ford y Fulkerson en 1956 en su artículo seminal “Flujo máximo a través de una red”, con la colaboración de otros matemáticos relevantes, como Claude Shannon, responsable del desarrollo de la teoría de la información. El teorema establece que el flujo máximo en una red es igual a la capacidad mínima de un corte, donde un corte es una partición de los nodos de la red en dos conjuntos disjuntos, y su capacidad es la suma de la capacidad de todas las aristas que cruzan el corte. Desde entonces, este teorema se ha convertido en un pilar de la teoría de redes de flujo.

• IA generativa para conocimientos biomédicos
• GPT-3 ¿Aprendizaje de pocos ejemplos para modelos de lenguaje?
• Ciencia de Datos Orientada a Objetos Refactorización de Código

Sin embargo, la introducción de este teorema va acompañada de otras contribuciones científicas clave como los algoritmos de Edmonds-Karp, Ford-Fulkerson o Dinic, que sirven para la tarea común de encontrar el flujo máximo que puede pasar a través de una red con una fuente y un sumidero. De manera similar, mediante el teorema de flujo máximo-mínimo, este valor coincide con el corte mínimo que divide el sumidero de la fuente. Además, podemos utilizar los cálculos internos de los algoritmos para identificar el conjunto de aristas que constituyen el corte mínimo, como exploraremos más adelante.

Redes de Flujo

Por lo tanto, para simplificar la explicación del teorema que sigue, primero conoceremos los fundamentos y conceptos indispensables sobre las redes de flujo en la teoría de grafos.

Como se puede ver en el ejemplo anterior, una red de flujo es un multigrafo dirigido ponderado utilizado para representar un objeto o sistema estructurado en red en el que una cierta cantidad de recursos, medida en lo que se denomina “flujo”, debe ser transmitida o movida desde uno o más puntos “fuente” (representada como el nodo S) hacia uno o más nodos denominados “sumidero” (nodo T). Aunque este ejemplo en particular no muestra la propiedad de multigrafo, ya que solo hay una arista entre dos nodos.

Para lograr la representación de una plantilla de este tipo, la red de flujo tiene pesos asociados a cada arista. En este contexto, las aristas ponderadas modelan una conexión física/lógica entre varios puntos de intercambio de recursos (flujo), donde el valor positivo real del peso representa su capacidad (flujo máximo admitido). Arriba, puedes ver la capacidad representada en el lado derecho de cada etiqueta de arista, así como el flujo actual que pasa, que en este caso es 0.

Además de la capacidad de cada arista, la métrica crucial que define la velocidad a la que los recursos atraviesan cada arista por unidad de tiempo es el flujo. Puedes pensarlo como el tráfico en una carretera o la cantidad de agua a través de un conducto. Por lo tanto, generado en los nodos fuente o nodo supersource si todas las fuentes de la red están conectadas a un generador de flujo maestro y llevado a los nodos sumidero o nodo supersink si se presenta una construcción similar en los sumideros, podemos definir el flujo como una función f:E→R que toma una arista (u,v) perteneciente al conjunto de aristas del grafo E y devuelve su flujo actual en el tiempo f(u,v), que es un valor real positivo.

Por lo tanto, si calculamos las expresiones anteriores para todas las fuentes S o sumideros T correspondientes a la red de flujo, podemos obtener la cantidad total de flujo que atraviesa el grafo.

Para garantizar que el flujo se adhiera a las restricciones de la red, debe cumplir dos propiedades fundamentales:

1. Restricción de capacidad: El flujo que pasa por cualquier arista no puede exceder su capacidad. Formalmente, si la capacidad de una arista se denota como “c(u, v)“, y el flujo a través de esa arista es “f(u, v)“, entonces debe cumplir la condición 0 ≤ f(u, v) ≤ c(u, v) para todas las aristas (u, v) dentro de la red. En pocas palabras, no podemos enviar más flujo a través de una arista que lo que su capacidad establece.
2. Conservación de flujo: En cada nodo (excluyendo los nodos fuente y sumidero), el flujo total que ingresa al nodo debe ser igual al flujo total que sale.

Esto garantiza que el flujo continúe sin interrupciones y no se acumule o disipe dentro de la red, aunque puedes permitir la acumulación de flujo si tu sistema lo requiere. Matemáticamente, para cada nodo “u” y sus nodos vecinos representados y agrupados por los supernodos “v y w“, la propiedad de conservación de flujo se expresa como:

Por último, ten en cuenta que los flujos pueden cancelarse entre sí, ya que si los flujos f1(u,v) y f2(v,u) coexisten entre 2 nodos u y v, entonces disminuir f1(u,v) es equivalente a aumentar f2(v,u), ya que tienen direcciones opuestas.

Redes Residuales y Caminos de Aumento

Aquí presentaremos dos conceptos nuevos y más sofisticados que serán de gran ayuda para encontrar flujos máximos utilizando los algoritmos mencionados anteriormente.

El primero de ellos es la diferencia entre la capacidad de una arista y su flujo en un momento dado, llamada capacidad residual y denotada como:

Con esa propiedad en mente, podemos proceder a definir un tipo particular de red de flujo denominada Red Residual, donde la única diferencia con una red estándar es la capacidad redefinida para sus aristas. Una red residual cuenta con la función cf definida anteriormente que asigna el conjunto de aristas, junto con sus respectivas capacidades y flujos, a la capacidad residual correspondiente.

En este ejemplo, tienes una red poblada con una función de flujo específica para todas sus aristas en el grafo superior. Por lo tanto, la red residual resulta ser la que está abajo, cuyas etiquetas de aristas contienen la capacidad residual que se puede enviar según la dirección de la arista correspondiente y la cantidad de flujo en la dirección opuesta que se podría entregar en caso de deshacer una acción de aumento de flujo (recuerda la propiedad de cancelación de flujo, que puede ser útil en situaciones donde la red tiene cierta simetría).

Aquí, el flujo logrado a través de la red se puede calcular con las fórmulas de origen o destino, como se vio antes, que en este caso son 7 unidades de flujo distribuidas en 4+3 unidades salientes desde S o igualmente 4+1+2 unidades entrantes en T. Sin embargo, si consideramos la arista (v5, v1) en dirección inversa (o bidireccional), existe la posibilidad de enviar 2 unidades de flujo más a lo largo del camino S-V1-V5-V4-V3-T, lo que aumentaría la cantidad total de flujo y se convertiría en la más grande disponible para la red dada. Posteriormente, después de haber derivado las redes residuales, existe la posibilidad de que en una o más rutas que conectan la fuente con el sumidero, todas las aristas tengan una capacidad residual mayor que 0. En otras palabras, hay rutas en las que podríamos transportar flujo desde una fuente hasta un sumidero, en el caso de que haya varias fuentes o sumideros.

Dentro de este contexto, dichas rutas subyacen en los algoritmos utilizados para resolver problemas de maximización de flujo o minimización de costos y se denominan Caminos de Aumento. Para entender por qué, en la red anterior, podemos ver cómo el flujo establecido conduce a la existencia de un camino de aumento mediante el cual se pueden transportar 2 unidades de flujo desde S hasta T. En consecuencia, la función de flujo actual sobre la red no proporciona el flujo máximo transportable a través de ella, lo cual es uno de los problemas que enfrenta el teorema Maxflow Mincut que discutiremos más adelante.

Como resultado, si aumentamos el flujo a lo largo del camino mostrado, podremos asegurar que el flujo resultante es máximo con un valor de 9 unidades, ya que no habrá otro camino para aumentar el flujo en la red. Finalmente, antes de presentar el teorema, es importante tener en cuenta que para encontrar el flujo máximo de una red, algoritmos como el de Ford-Fulkerson utilizan un procedimiento intuitivo (ávido) que parte de una red residual sin flujo y procede a encontrar caminos de aumento (con la ayuda de aristas residuales o flujos en dirección opuesta) mientras aumenta el flujo determinado por estos caminos. Así, una vez que no hay más caminos por descubrir que aumenten el flujo, se puede asegurar que el flujo alcanzado es el máximo, es decir, que no hay una forma más rápida de mover recursos desde S hasta T debido a la falta de capacidad en algunas aristas o incluso a la falta de aristas en la red.

Otra forma de pensar en este procedimiento es considerar la cantidad de flujo agregada por iteración. Para un camino de aumento arbitrario, la cantidad más alta que puedes agregar está dada por la arista con la menor capacidad residual, ya que constituye un cuello de botella para el flujo fuera de S. Debido a su capacidad para limitar todo el flujo potencial a lo largo de un camino de aumento, tal Arista de Cuello de Botella es clave en situaciones donde necesitamos maximizar el flujo.

Por ejemplo, considerando la red de flujo simple superior (residual) con solo una ruta de aumento disponible, podemos identificar claramente el componente de cuello de botella de la arista (v2, v3), que establece el flujo máximo de toda la ruta (y en este caso de la red) a 3. Después de aumentar el flujo en 3 unidades según indica la ruta, no hay más rutas de aumento para aumentar aún más el flujo, por lo que se concluye que se ha alcanzado el flujo máximo. Sin embargo, otra forma de asegurar la validación del flujo resultante es enfocarse en los cuellos de botella dentro de la red; si cada ruta entre S y T tiene un valor de cuello de botella nulo, es decir, su capacidad residual máxima igual a 0, lo cual es equivalente a la no existencia de rutas de aumento, no se puede agregar más flujo y se considerará que el flujo actual es máximo, como se mostró anteriormente.

Para resolver la pregunta sobre los cuellos de botella, debemos destacar que el flujo máximo también se puede expresar como la suma de los cuellos de botella de todas las rutas de aumento utilizadas para encontrar el flujo máximo a través de algoritmos similares a Ford-Fulkerson, ya que cada ruta agrega tanto flujo como determinado por su cuello de botella correspondiente.

Cortes de Red de Flujo

La última parte que cubriremos en relación a los fundamentos de las redes de flujo serán los cortes, un componente fundamental del teorema de Maxflow-Mincut y un concepto clave para comprender las secciones anteriores debido, por ejemplo, a la relación entre los cuellos de botella y las particiones de una red de flujo.

En primer lugar, comencemos con su definición; un corte es una partición de los nodos de la red donde el nodo fuente S está en un conjunto A y el sumidero T está en otro conjunto B disjunto al anterior.

Ni el conjunto A ni el conjunto B pueden estar vacíos, ya que deben contener el/los nodo(s) fuente y el/los nodo(s) sumidero, respectivamente. Por lo tanto, si la red está conectada, habrá aristas que realizan la funcionalidad de conexión entre los nodos de A y B de manera bidireccional. Además, estas aristas están contenidas en otro conjunto llamado conjunto de corte, aunque solo se tienen en cuenta aquellas cuyo origen es un nodo en A y termina en B, es decir, aristas capaces de transportar flujo en la dirección correcta.

Como ejemplo, arriba puedes ver el corte más simple que podemos aplicar al grafo, lo que resulta en una partición del conjunto de vértices V como la unión de los conjuntos A={S} y B={V1,V2,V3,V4,V5,T}. Como la fuente única de la red permanece aislada en un conjunto, podemos comprender de manera más precisa el concepto de corte y sus propiedades posteriores. Típicamente, el corte se representa como una línea que busca encerrar uno de los dos conjuntos A o B, indistintamente. Además, el límite divisorio atraviesa múltiples aristas que forman parte del conjunto de corte, en ambas direcciones. Estas aristas se utilizan para determinar el flujo y la capacidad del corte, que son componentes esenciales al establecer una relación entre un corte arbitrario de la red y el flujo. Esto es crucial para demostrar el teorema presentado en este artículo.

Por un lado, el flujo a través de cualquier corte dado se define como la suma de todas las aristas que transportan flujo en la dirección A-B, menos el flujo de las aristas que van en dirección opuesta desde el conjunto B al conjunto A.

Sin embargo, el flujo no ofrece un valor significativo en este contexto, ya que está limitado por la capacidad del corte. Por esta razón, también podemos definir la capacidad de un corte de manera similar al flujo, con la diferencia de que aquí solo se tiene en cuenta el primer término de la fórmula anterior, es decir, la capacidad de las aristas que son capaces de transportar el flujo de S a T, sin tener que restar ningún otro valor de arista.

Una vez que hemos presentado formalmente el concepto de flujo y capacidad en los cortes, se vuelve necesario considerar algunos ejemplos para simplificar estas ideas tanto como sea posible y comprender su fundamentación en esta área.

Primero, examinemos los vértices de cada conjunto, dejando A={S,V5,V4} y B={V1,V2,V3,T}. Dado que a la red ya se le ha asignado un flujo, entonces el flujo del corte no será cero y se determinará por la suma de los flujos en las aristas que conectan el conjunto A con el conjunto B.

Además, su capacidad se obtiene de las mismas aristas anteriores y sus respectivas capacidades, constituyendo el flujo máximo que podría transitar por el corte.

En este interesante último ejemplo de corte, se puede observar cómo un corte no tiene que ser una división en la que los vértices de ambos conjuntos formen componentes conectados, es decir, cada conjunto puede contener cualquier nodo siempre y cuando se cumplan las restricciones básicas de un corte.

Además, este ejemplo es particularmente útil para comprender la relación entre los cortes y el flujo, proporcionando una base sólida antes de abordar el teorema. Primero, hay que tener en cuenta que, según la definición de corte, la red resultante (después del corte) está desconectada con respecto a s-t. Esto significa que la capacidad de dicho corte se calcula como la suma de todas las aristas que van desde el conjunto fuente hasta el sumidero. En el caso más básico de aislar la única fuente de flujo, la capacidad del corte será mayor o igual al flujo máximo de la red. Sin embargo, en los ejemplos anteriores se puede apreciar que al insertar más nodos con aristas salientes, la capacidad del corte aumenta inevitablemente, ya que hay más aristas de las estrictamente necesarias para alcanzar el flujo máximo, es decir, las aristas de la fuente son las que determinan, en el caso de los cuellos de botella, el flujo que posteriormente recorrerá la red.

Enunciado del Teorema

Nuestro objetivo principal al abordar un desafío de optimización de redes de flujo es determinar el flujo máximo alcanzable que se puede transmitir desde la fuente hasta el sumidero. Esto debe lograrse cumpliendo las limitaciones de capacidad, conservación de flujo y asegurando que el flujo alcanzado sea realmente máximo. Por lo tanto, el paso que daremos al abordar el teorema será restringir ese valor con un límite superior que se puede calcular de manera aproximada similar al flujo y confirmar así su corrección.

Inicialmente, cabe destacar que dicho límite superior resulta ser un corte, que cumple con la propiedad de ser aquel con la menor capacidad. Siendo el lema principal del teorema, puede que no quede del todo claro, así que vamos a introducir y demostrar dos ideas más simples;

El primero involucra demostrar la igualdad anterior entre el flujo a través de cualquier corte dado y el flujo total de la red, que a su vez coincide con el flujo generado por la fuente. Para este propósito, podemos suponer la proposición inicial como verdadera mientras aplicamos el método de inducción al conjunto A de cualquier corte, con A = {S} como caso base, y luego usar el principio previamente mencionado de conservación del flujo para nodos diferentes de S o T. Pero dado que esto sería complejo de elaborar, optaremos por un enfoque más simple, aunque muy similar.

Tenga en cuenta que el valor de flujo anterior a lo largo de la prueba puede tener cualquier valor permitido.

1- Definición de flujo: En el paso inicial, comenzamos con el valor total de flujo para cualquier función de flujo dada f en una red y una de sus posibles definiciones. Aquí, tomando como referencia el nodo fuente S, que es el conjunto A más pequeño posible para cualquier corte de red, igualamos el valor del flujo al flujo generado por S menos el flujo entrante en S, ya que a veces puede haber una cierta cantidad de flujo que regresa a S.

2- Propiedad de conservación del flujo: Después de considerar el flujo de la red como el flujo total generado por la fuente S, aplicamos el principio de conservación del flujo según el cual todos los nodos, excepto s-t, deben propagar todo el flujo que reciben, lo que resulta en un flujo cero contribuido a |f| al restar el flujo saliente menos el flujo entrante. Ahora, si tomamos cualquier corte (A,B), el flujo total contribuido por los nodos v dentro del conjunto A excepto el que genera el flujo {S} será cero, satisfaciendo la igualdad que teníamos antes.

3- Flujo a través del corte: Finalmente, llegamos a una expresión donde sumamos todo el flujo saliente de los nodos de A excepto S en el segundo término y el flujo saliente propio de S en el primer término, restando la parte entrante correspondiente de todos los nodos anteriores. Esto corresponde a la definición mencionada anteriormente de flujo del corte, y por lo tanto podemos concluir como consecuencia que todo el flujo existente a través de una red necesariamente coincidirá con el flujo a través de cualquier corte dado.

La segunda proposición que demostraremos con respecto al teorema Maxflow Mincut comprende una desigualdad que limita superiormente el valor de cualquier flujo en una red con el valor de capacidad para cualquier corte dado.

1- Definición alternativa de flujo: Usando el resultado anterior con respecto al flujo de cualquier corte, podemos igualar un flujo arbitrario |f| al flujo a través de un corte arbitrario (A,B).

2/3- Límite del flujo: En el segundo paso, establecemos una desigualdad que prescinde del segundo término que modela el flujo entrante en el conjunto A, dejando solo el flujo saliente de las aristas que llevan flujo de A a B. Después de eliminar dicho término, el resultado siempre será mayor o igual al anterior, ya que si no hay una arista que devuelva flujo de B a A, la suma del flujo de las aristas restantes de A a B no disminuirá.

Luego, simplemente podemos aumentar el valor de la desigualdad estableciendo que el flujo de las aristas salientes de A sea menor o igual a la capacidad de esas aristas. La validez de esta desigualdad se basa en la restricción de capacidad que aparece en todas las aristas de la red.

4- Dualidad débil: Después de igualar la suma de capacidad de todas las aristas salientes del conjunto A con la capacidad del corte debido a su definición, se puede concluir que para cualquier flujo y corte dados en una red, el flujo siempre será menor o igual a la capacidad del corte, lo cual resulta ser el punto de partida del teorema que estamos a punto de demostrar. Además, si intentamos maximizar el flujo, llegaremos a un punto que puede ser satisfecho al minimizar una capacidad de corte, estableciendo una relación débilmente dual donde no hay certeza de que siempre exista un corte de capacidad mínima igual a un flujo máximo.

En este punto, después de haber alcanzado la dualidad débil previa al teorema Maxflow Mincut, podemos presentar una afirmación que es más fácil de comprender y verificar.

Como ya se mencionó, el teorema se cumple a través de la dualidad fuerte que el flujo máximo en cualquier red coincide con el corte de menor capacidad alcanzable. A diferencia del resultado dual débil anterior, este teorema asegura que la maximización del flujo dual es exactamente igual a la minimización de la capacidad de cualquier corte, eliminando la posibilidad de tener una diferencia entre los dos resultados y otorgando una condición fuertemente dual al lema.

Antes de proceder con su demostración, debemos resaltar un caso de uso para el teorema. Aquí, el flujo máximo tiene un valor de 7, que es igual a la suma de la capacidad de cada arista de corte saliente. Tenga en cuenta que estas aristas llevan flujo a su capacidad máxima, lo que, en un corte de capacidad mínima como el mostrado, hace que estas aristas sean cuellos de botella, es decir, el conjunto de corte en sí actúa como un cuello de botella del flujo de red global. Para resumir la explicación de esta idea, encontrará a continuación un recurso que le ayudará a comprenderlo:

¿Cuál es una explicación intuitiva del teorema de flujo máximo y corte mínimo?

Estoy a punto de leer la demostración del teorema de flujo máximo y corte mínimo que ayuda a resolver el problema del flujo máximo en la red. ¿Podría…?

math.stackexchange.com

Demostración

Si queremos demostrar que el flujo máximo en la red es igual, en todos los casos, al corte de capacidad mínima en una red, utilizaremos 3 proposiciones que deben ser equivalentes para que el teorema sea verdadero.

Existe un corte (A, B) que satisface |f|= cap(A, B).

El valor del flujo |f| es máximo.

No existe un camino de aumento en la red de flujo.

Para mostrar que todas las afirmaciones son equivalentes, demostraremos las implicaciones lógicas 1⇒2⇒3⇒1. Lo que significa que podemos inferir cualquier afirmación a partir de cualquier otra afirmación. En el caso de 1⇒2, se puede verificar fácilmente utilizando la dualidad débil mostrada anteriormente. Luego, considerando que cualquier flujo es menor que el corte de menor capacidad, si asumimos que existe un flujo igual a la capacidad de un corte arbitrario (1), la dualidad débil nos dice que esta capacidad es el límite superior para cualquier flujo dado y, por lo tanto, el flujo resultante, coincidente con ese límite, es máximo (2).

Continuando con 2⇒3, la forma más sencilla de verificarlo es tomar la contrapositiva ¬3⇒¬2. Entonces, basta con tomar un flujo arbitrario |f| como ejemplo, en caso de que hubiera un camino de aumento s-t ¬(3) que pudiera transportar flujo, |f| podría aumentarse a lo largo del camino correspondiente, lo que implica que |f| no era originalmente el flujo máximo ¬(2).

Finalmente, el paso más desafiante en esta demostración es 3⇒1. Primero, comenzamos asumiendo un flujo |f| en el que la red no tiene caminos de aumento. Además, definimos un conjunto A que contiene todos los vértices alcanzables desde S en la red residual. Es decir, A contiene todos los vértices a los que existe un camino desde S en la red residual, y al mismo tiempo, todas las aristas residuales de ese camino son diferentes de cero. A través de estas definiciones, podemos estar seguros de que S está en A ya que es autoalcanzable, y dado que no hay caminos de aumento, T no es alcanzable en la red residual desde S, por lo que sabemos que al menos un nodo (T) no está en el conjunto A. Luego, si insertamos T en un conjunto diferente B, entonces tenemos que el par (A, B) cumple con todos los criterios para ser un corte válido en la red.

En este punto, debemos darnos cuenta de dos cosas sobre la cortada (A, B). Por un lado, el flujo a través de la cortada en la dirección S-T debe ser igual a su capacidad. Debido a las definiciones y suposiciones anteriores (3), la única posibilidad de que no sean iguales radica en la accesibilidad de los nodos de B, por lo que si alguno de ellos fuera accesible desde S en la red residual, causando que el flujo en el borde de la cortada no alcance su capacidad total, el nodo tendría que estar dentro de A en lugar de B, lo cual es una contradicción. Por otro lado, el flujo en la otra dirección de la cortada resulta ser cero debido a la misma razón anterior, es decir, si no fuera cero, habría un borde en la red residual en la dirección A-B (flujo del borde residual representado con signo negativo) que llegaría al nodo en B y causaría la contradicción.

Por último, lo único que queda por hacer es igualar el flujo de la red al flujo de la cortada, lo cual se demostró anteriormente, eliminar el término del flujo en la cortada ya que es nulo, y usar la definición de capacidad de la cortada para concluir que el flujo |f| es igual a la capacidad resultante de la cortada (3⇒1).

Aplicaciones

El Teorema de Flujo Máximo – Corte Mínimo tiene numerosas aplicaciones en varios campos. Sin embargo, para ser breve, simplemente mencionaremos algunos aspectos esenciales de los casos de uso, junto con recursos más detallados para ayudarte a entenderlos correctamente.

Algoritmos Ford-Fulkerson/Edmonds-Karp

Como primera consecuencia, los hallazgos y resultados proporcionados por el teorema, en conjunto con otros como el teorema de integridad, conducen y respaldan la prueba de corrección de una serie de algoritmos orientados a calcular el flujo máximo.

El más significativo de estos, y del cual ya hemos hablado, es el algoritmo de Ford Fulkerson, un enfoque greedy que aumenta el flujo buscando caminos de aumento de s-t. Sin embargo, la versión más básica del algoritmo no tiene garantía de terminar o converger al flujo máximo en ciertas situaciones con entradas muy específicas (como trabajar con números reales o irracionales y su representación) debido a la forma en que elige los caminos de aumento. Esto también influye en su complejidad temporal, que es de O(|E| |f|), lo que significa que en el peor de los casos, el algoritmo necesita recorrer todos los bordes de la red por cada unidad de flujo contenida en el máximo a alcanzar.

Luego, con el objetivo de mejorar la versión anterior, que fue la primera creada para resolver problemas de este tipo, se mejoró la forma de calcular los caminos de aumento. De tal manera que, mientras la versión Ford-Fulkerson utilizaba la búsqueda en profundidad (DFS), que calcula caminos aleatorios a T, la variante mejorada Edmonds-Karp se implementa utilizando el algoritmo de búsqueda en anchura (BFS) para encontrar caminos de aumento. Así, con el objetivo de elegir en cada iteración el camino de aumento con la menor cantidad posible de bordes, el algoritmo tiene una garantía de terminación con respecto al anterior, además de un cambio en la complejidad temporal del orden de O(V E²).

No obstante, con estos y otros algoritmos similares, es posible calcular no solo el flujo máximo en una red, sino también el corte mínimo cuya capacidad es igual a su valor. El procedimiento es bastante simple; después de calcular el flujo máximo en todos los bordes de una red, según el teorema de Flujo Máximo – Corte Mínimo, los nodos accesibles desde S en la red residual resultante forman el conjunto A del corte que estamos buscando, siendo los nodos restantes B y llevando al corte de capacidad mínima resultante (A, B).

Finalmente, cabe destacar que el campo de estudio de los algoritmos de flujo máximo es mucho más amplio de lo que se muestra aquí. Por lo tanto, si deseas seguir aprendiendo, aquí tienes un recurso que aborda estos algoritmos, así como sus implementaciones, con más detalle.

Casos de uso prácticos

Casi todos los sistemas con los que interactuamos en nuestras vidas tienen potencial para ser modelados (al menos en parte) por redes de flujo, lo que los convierte en una herramienta crucial para abordar problemas complejos de escalabilidad. Asimismo, dado que las posibilidades son amplias, aquí se mencionarán solo algunos de ellos que tienen una relación directa con los conceptos fundamentales.

Inicialmente, todos los sistemas de transporte, desde redes de carreteras y sistemas de transporte público hasta enrutamiento de aerolíneas y distribución de carga, pueden ser representados como redes de flujo. Como resultado, podemos analizar los patrones de tráfico, optimizar rutas y mejorar la eficiencia general. Esto es particularmente crucial en la planificación urbana, donde gestionar el flujo de personas, vehículos y mercancías es esencial para prevenir la congestión y garantizar un funcionamiento fluido. Además, no todos estos casos de uso son totalmente beneficiosos; por ejemplo, las redes de flujo también pueden modelar el sistema ferroviario de un país, que puede ser objetivo de ataques estratégicamente óptimos en caso de conflicto militar. Puedes obtener más información sobre esta aplicación específica en este recurso.

A pesar de otras implementaciones trascendentales en telecomunicaciones, distribución de energía e incluso atención médica, nos centraremos en una más estrechamente relacionada con la informática, específicamente con el campo de la visión por computadora, que ha logrado avances significativos. En el procesamiento de imágenes, la principal aplicación de las redes de flujo se basa en algoritmos de segmentación de imágenes, que se encargan de dividir una imagen en segmentos o regiones que corresponden a objetos, sujetos o áreas distintas necesarias para detectar, las cuales quizás no se pueden distinguir a simple vista. En este contexto, las redes de flujo aportan su capacidad modelando las relaciones entre los píxeles como una red, donde las aristas representan el flujo de valores de probabilidad de similitud/desemejanza entre píxeles vecinos. Además, también vale la pena mencionar las aplicaciones en ámbitos comparables, como modelos de aprendizaje automático, en los que el concepto de flujo se utiliza para optimizar tareas específicas de aprendizaje, generación o clasificación.

Conclusión

Este artículo ha abarcado una fracción menor del dominio matemático de las redes de flujo, así como ha demostrado y simplificado uno de sus teoremas fundamentales. Sin embargo, dado que es un tema con una gran cantidad de aplicaciones, especialmente en el sistema mundial de consumo, transporte y gestión de la población, es útil seguir ampliando la teoría y profundizando en el conocimiento sobre estas aplicaciones. Con este propósito, los recursos más eficientes para observar formalizaciones más avanzadas del teorema, así como para comprender paso a paso los algoritmos mencionados en este artículo y aprender nuevos conceptos sobre ciertas aplicaciones de las redes de flujo, son los siguientes:

https://www.cs.upc.edu/~mjserna/docencia/grauA/P20/MaxFlow-fib.pdf

https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Introduction_to_Network_Flow.pdf

We will continue to update Zepes; if you have any questions or suggestions, please contact us!