En la teoría de la optimización , los problemas de flujo máximo implican encontrar un flujo factible a través de una red de flujo que obtenga el máximo caudal posible.
El problema del flujo máximo puede verse como un caso especial de problemas de flujo de red más complejos, como el problema de circulación . El valor máximo de un flujo st (es decir, el flujo desde la fuente s hasta el sumidero t) es igual a la capacidad mínima de un corte st (es decir, el corte que separa s de t) en la red, como se indica en el flujo máximo mínimo. teorema de corte .
El problema del flujo máximo fue formulado por primera vez en 1954 por TE Harris y FS Ross como un modelo simplificado del flujo de tráfico ferroviario soviético. [1] [2] [3]
En 1955, Lester R. Ford, Jr. y Delbert R. Fulkerson crearon el primer algoritmo conocido, el algoritmo Ford-Fulkerson . [4] [5] En su artículo de 1955, [4] Ford y Fulkerson escribieron que el problema de Harris y Ross se formula de la siguiente manera (ver [1] p. 5):
Considere una red ferroviaria que conecta dos ciudades a través de varias ciudades intermedias, donde cada enlace de la red tiene asignado un número que representa su capacidad. Suponiendo una condición de estado estacionario, encuentre un flujo máximo de una ciudad dada a la otra.
En su libro Flows in Network , [5] de 1962, Ford y Fulkerson escribieron:
Se lo planteó a los autores en la primavera de 1955 TE Harris, quien, junto con el general FS Ross (retirado), había formulado un modelo simplificado de flujo de tráfico ferroviario y había señalado este problema particular como el central sugerido por el modelo [11].
donde [11] se refiere al informe secreto de 1955 Fundamentos de un método para evaluar las capacidades netas ferroviarias de Harris y Ross [3] (ver [1] p. 5).
A lo largo de los años, se descubrieron varias soluciones mejoradas al problema del flujo máximo, en particular el algoritmo de ruta de aumento más corto de Edmonds y Karp y, de forma independiente, Dinitz; el algoritmo de bloqueo de flujo de Dinitz; el algoritmo push-relabel de Goldberg y Tarjan ; y el algoritmo de flujo de bloqueo binario de Goldberg y Rao. Los algoritmos de Sherman [6] y Kelner, Lee, Orecchia y Sidford, [7] [8] respectivamente, encuentran un flujo máximo aproximadamente óptimo pero sólo funcionan en grafos no dirigidos.
En 2013, James B. Orlin publicó un artículo que describe un algoritmo. [9]
En 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg y Sushant Sachdeva publicaron un algoritmo de tiempo casi lineal para el problema de flujo de costo mínimo, del cual el problema de flujo máximo es un caso particular. . [10] [11] Para el problema del camino más corto de fuente única (SSSP) con pesos negativos, también se ha informado de otro caso particular de problema de flujo de costo mínimo, un algoritmo en tiempo casi lineal. [12] [13] Ambos algoritmos fueron considerados los mejores artículos en el Simposio sobre fundamentos de la informática de 2022 . [14] [15]
Primero establecemos alguna notación:
Definición. La capacidad de un borde es la cantidad máxima de flujo que puede pasar a través de un borde. Formalmente es un mapa.
Definición. Un flujo es un mapa que satisface lo siguiente:
Observación . Los flujos son sesgadamente simétricos: para todos
Definición. El valor del flujo es la cantidad de flujo que pasa desde la fuente al sumidero. Formalmente para un flujo viene dado por:
Definición. El problema del flujo máximo es encaminar la mayor cantidad de flujo posible desde la fuente al sumidero; en otras palabras, encontrar el flujo con el valor máximo.
Tenga en cuenta que pueden existir varios flujos máximos, y si se permiten valores de flujo reales arbitrarios (o incluso racionales arbitrarios) (en lugar de sólo números enteros), hay exactamente un flujo máximo, o infinitos, ya que hay infinitas combinaciones lineales de flujos máximos. los caudales máximos base. En otras palabras, si enviamos unidades de flujo en el borde en un flujo máximo y unidades de flujo en otro flujo máximo, entonces para cada uno podemos enviar unidades y enrutar el flujo en los bordes restantes en consecuencia, para obtener otro flujo máximo. Si los valores de flujo pueden ser números reales o racionales, entonces hay infinitos valores de este tipo para cada par .
La siguiente tabla enumera algoritmos para resolver el problema de flujo máximo. Aquí, y denota el número de vértices y aristas de la red. El valor se refiere a la capacidad de borde más grande después de reescalar todas las capacidades a valores enteros (si la red contiene capacidades irracionales , puede ser infinita).
Para algoritmos adicionales, consulte Goldberg y Tarjan (1988).
El teorema del flujo integral establece que
La afirmación no es sólo que el valor del flujo es un número entero, lo que se deriva directamente del teorema del corte mínimo del flujo máximo , sino que el flujo en cada borde es integral. Esto es crucial para muchas aplicaciones combinatorias (ver más abajo), donde el flujo a través de un borde puede codificar si el elemento correspondiente a ese borde debe incluirse en el conjunto buscado o no.
Dada una red con un conjunto de fuentes y un conjunto de sumideros en lugar de una sola fuente y un sumidero, debemos encontrar el flujo máximo a través de . Podemos transformar el problema de múltiples fuentes y múltiples sumideros en un problema de flujo máximo agregando una fuente consolidada que se conecta a cada vértice y un sumidero consolidado conectado por cada vértice (también conocido como superfuente y supersumidero ) con capacidad infinita en cada borde ( Ver Fig. 4.1.1.).
Dado un gráfico bipartito , debemos encontrar una coincidencia de cardinalidad máxima en , es decir, una coincidencia que contiene el mayor número posible de aristas. Este problema se puede transformar en un problema de flujo máximo construyendo una red , donde
Entonces, el valor del flujo máximo en es igual al tamaño de la coincidencia máxima en , y se puede encontrar una coincidencia de cardinalidad máxima tomando aquellos bordes que tienen flujo en un flujo máximo integral.
Dado un gráfico acíclico dirigido , debemos encontrar el número mínimo de caminos disjuntos de vértices para cubrir cada vértice . Podemos construir un gráfico bipartito a partir de , donde
Luego se puede demostrar que tiene una coincidencia de tamaño si y solo si tiene una cobertura de ruta disjunta con vértices que contiene bordes y rutas, donde es el número de vértices en . Por lo tanto, el problema se puede resolver encontrando la cardinalidad máxima que coincida .
Supongamos que hemos encontrado una coincidencia de y construimos la portada a partir de ella. Intuitivamente, si dos vértices coinciden en , entonces el borde está contenido en . Claramente el número de aristas es . Para ver que es un vértice disjunto, considere lo siguiente:
Por lo tanto, ningún vértice tiene dos aristas entrantes o dos salientes en , lo que significa que todos los caminos en son separados de vértices.
Para mostrar que la portada tiene tamaño , comenzamos con una portada vacía y la construimos de forma incremental. Para agregar un vértice a la portada, podemos agregarlo a un camino existente o crear un nuevo camino de longitud cero comenzando en ese vértice. El primer caso es aplicable siempre que alguna ruta en la portada comience en o alguna ruta termine en . Este último caso siempre es aplicable. En el primer caso, el número total de aristas de la cubierta aumenta en 1 y el número de caminos permanece igual; en el último caso, el número de caminos aumenta y el número de aristas permanece igual. Ahora está claro que después de cubrir todos los vértices, la suma del número de caminos y aristas en la cubierta es . Por lo tanto, si el número de aristas en la cubierta es , el número de caminos es .
Sea una red. Supongamos que hay capacidad en cada nodo además de la capacidad de borde, es decir, un mapeo tal que el flujo tiene que satisfacer no sólo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad de vértice.
En otras palabras, la cantidad de flujo que pasa por un vértice no puede exceder su capacidad. Para encontrar el flujo máximo a través , podemos transformar el problema en el problema de flujo máximo en el sentido original expandiendo . Primero, cada uno se reemplaza por y , donde está conectado por los bordes que entran y está conectado con los bordes que salen de , luego asigna capacidad al borde que conecta y (ver Fig. 4.4.1). En esta red expandida, la restricción de capacidad del vértice se elimina y, por lo tanto, el problema puede tratarse como el problema de flujo máximo original.
Dado un gráfico dirigido y dos vértices y , debemos encontrar el número máximo de caminos desde hasta . Este problema tiene varias variantes:
1. Los caminos deben estar separados de los bordes. Este problema se puede transformar en un problema de flujo máximo construyendo una red desde , siendo y la fuente y el sumidero de respectivamente, y asignando a cada borde una capacidad de . En esta red, el flujo máximo es si hay caminos de borde disjunto.
2. Los caminos deben ser independientes, es decir, separados por vértices (excepto y ). Podemos construir una red con capacidades de vértices, donde las capacidades de todos los vértices y todas las aristas son . Entonces el valor del flujo máximo es igual al número máximo de caminos independientes desde a .
3. Además de que los caminos son disjuntos en los bordes y/o en los vértices, los caminos también tienen una restricción de longitud: solo contamos los caminos cuya longitud es exactamente , o como máximo . La mayoría de las variantes de este problema son NP completas, excepto valores pequeños de . [26]
Un cierre de un gráfico dirigido es un conjunto de vértices C , tal que ninguna arista sale de C . El problema de cierre es la tarea de encontrar el cierre de peso máximo o mínimo en un gráfico dirigido ponderado por vértices. Puede resolverse en tiempo polinómico utilizando una reducción al problema de flujo máximo.
En el problema de eliminación de béisbol hay n equipos compitiendo en una liga. En una etapa específica de la temporada de la liga, w i es el número de victorias y r i es el número de juegos que quedan por jugar para el equipo i y r ij es el número de juegos que quedan contra el equipo j . Un equipo queda eliminado si no tiene posibilidades de terminar la temporada en primer lugar. La tarea del problema de eliminación del béisbol es determinar qué equipos son eliminados en cada punto de la temporada. Schwartz [27] propuso un método que reduce este problema al flujo máximo de la red. En este método se crea una red para determinar si el equipo k es eliminado.
Sea G = ( V , E ) una red en la que s , t ∈ V sea la fuente y el sumidero respectivamente. Se agrega un nodo de juego ij , que representa el número de jugadas entre estos dos equipos. También agregamos un nodo de equipo para cada equipo y conectamos cada nodo de juego { i , j } con i < j a V , y conecta cada uno de ellos desde s por un borde con capacidad r ij - que representa el número de jugadas entre estos dos equipos. También agregamos un nodo de equipo para cada equipo y conectamos cada nodo de juego { i , j } con dos nodos de equipo i y j para asegurar que uno de ellos gane. No es necesario restringir el valor del flujo en estos bordes. Finalmente, se hacen bordes desde el nodo del equipo i hasta el nodo sumidero t y la capacidad de w k + r k – wi se establece para evitar que el equipo i gane más que w k + r k . Sea S el conjunto de todos los equipos que participan en la liga y sea
En este método se afirma que el equipo k no se elimina si y sólo si existe un valor de flujo de tamaño r ( S − { k }) en la red G. En el artículo mencionado se demuestra que este valor de flujo es el valor de flujo máximo de s a t .
En la industria aérea un problema importante es la programación de las tripulaciones de vuelo. El problema de programación de líneas aéreas puede considerarse como una aplicación del flujo máximo extendido de la red. La entrada de este problema es un conjunto de vuelos F que contiene información sobre dónde y cuándo sale y llega cada vuelo. En una versión de programación de líneas aéreas, el objetivo es producir un horario factible con como máximo k tripulaciones.
Para resolver este problema se utiliza una variación del problema de circulación llamada circulación acotada, que es la generalización de los problemas de flujo de red , con la restricción adicional de un límite inferior en los flujos de borde.
Sea G = ( V , E ) una red con s , t ∈ V como nodos fuente y sumidero. Para el origen y el destino de cada vuelo i , se agregan dos nodos a V , el nodo s i como origen y el nodo d i como nodo destino del vuelo i . También se agregan las siguientes aristas a E :
En el método mencionado, se afirma y demuestra que encontrar un valor de flujo de k en G entre s y t es igual a encontrar un horario factible para el conjunto de vuelos F con como máximo k tripulaciones. [28]
Otra versión de la programación de aerolíneas es encontrar las tripulaciones mínimas necesarias para realizar todos los vuelos. Para encontrar una respuesta a este problema, se crea un gráfico bipartito G' = ( A ∪ B , E ) donde cada vuelo tiene una copia en el conjunto A y el conjunto B. Si el mismo avión puede realizar el vuelo j después del vuelo i , i ∈ A está conectado a j ∈ B. Una coincidencia en G' induce un horario para F y, obviamente, la máxima coincidencia bipartita en este gráfico produce un horario de aerolínea con un número mínimo de tripulaciones. [28] Como se menciona en la parte de Aplicación de este artículo, la coincidencia bipartita de cardinalidad máxima es una aplicación del problema de flujo máximo.
Hay algunas fábricas que producen bienes y algunas aldeas donde se deben entregar los bienes. Están conectados por una red de caminos y cada camino tiene una capacidad c para el máximo de mercancías que pueden fluir a través de él. El problema es encontrar si existe una circulación que satisfaga la demanda. Este problema puede transformarse en un problema de flujo máximo.
Sea G = ( V , E ) esta nueva red. Existe una circulación que satisface la demanda si y sólo si:
Si existe una circulación, observar la solución de flujo máximo daría la respuesta sobre cuántas mercancías deben enviarse por una carretera particular para satisfacer las demandas.
El problema se puede ampliar agregando un límite inferior al flujo en algunos bordes. [29]
Kleinberg y Tardos presentan en su libro un algoritmo para segmentar una imagen. [31] Presentan un algoritmo para encontrar el fondo y el primer plano en una imagen. Más precisamente, el algoritmo toma un mapa de bits como entrada modelado de la siguiente manera: a i ≥ 0 es la probabilidad de que el píxel i pertenezca al primer plano, bi ≥ 0 en la probabilidad de que el píxel i pertenezca al fondo, y p ij es el penalización si dos píxeles adyacentes i y j se colocan uno en primer plano y el otro en segundo plano. El objetivo es encontrar una partición ( A , B ) del conjunto de píxeles que maximice la siguiente cantidad
De hecho, para los píxeles en A (considerados como primer plano), obtenemos a i ; para todos los píxeles en B (considerados como fondo), ganamos bi . En el borde, entre dos píxeles adyacentes i y j , soltamos p ij . Equivale a minimizar la cantidad.
porque
Ahora construimos la red cuyos nodos son el píxel, más una fuente y un sumidero, consulte la figura de la derecha. Conectamos la fuente al píxel i por un borde de peso a i . Conectamos el píxel i al sumidero por un borde de peso b i . Conectamos el píxel i al píxel j con peso p ij . Ahora queda calcular un corte mínimo en esa red (o equivalentemente un flujo máximo). La última figura muestra un corte mínimo.
1. En el problema de flujo de costo mínimo , cada arista ( u ,v) también tiene un coeficiente de costo auv además de su capacidad. Si el flujo a través del borde es f uv , entonces el costo total es a uv f uv . Se requiere encontrar un flujo de un tamaño dado d , con el menor costo. En la mayoría de las variantes, los coeficientes de costos pueden ser positivos o negativos. Existen varios algoritmos de tiempo polinomial para este problema.
2. El problema del flujo máximo puede verse aumentado por restricciones disyuntivas : una restricción disyuntiva negativa dice que un cierto par de aristas no pueden tener simultáneamente un flujo distinto de cero; Una restricción disyuntiva positiva dice que, en un determinado par de aristas, al menos una debe tener un flujo distinto de cero. Con restricciones negativas, el problema se vuelve fuertemente NP-difícil incluso para redes simples. Con restricciones positivas, el problema es polinómico si se permiten flujos fraccionarios, pero puede ser fuertemente NP-difícil cuando los flujos deben ser integrales. [32]
{{cite book}}
: CS1 maint: multiple names: authors list (link)