Teorema de corte mínimo de flujo máximo aproximado

Los teoremas aproximados de flujo máximo y corte mínimo son proposiciones matemáticas en la teoría del flujo de red . Se ocupan de la relación entre el caudal máximo ("flujo máximo") y el corte mínimo (" corte mínimo ") en un problema de flujo de múltiples productos básicos . Los teoremas han permitido el desarrollo de algoritmos de aproximación para su uso en la partición de gráficos y problemas relacionados.

Un "producto" en un problema de flujo de red es un par de nodos fuente y sumidero . En un problema de flujo de múltiples productos básicos, hay $k\geq1$ productos básicos, cada uno con su propia fuente , sumidero y demanda . El objetivo es enrutar simultáneamente unidades del producto $i$ de a para cada $i$ , de modo que la cantidad total de todos los productos que pasan por cualquier borde no sea mayor que su capacidad. (En el caso de bordes no dirigidos, la suma de los flujos en ambas direcciones no puede exceder la capacidad del borde). ^[1] Especialmente, un problema de flujo de un solo producto (o un solo producto) también se conoce como problema de flujo máximo . De acuerdo con la ${\ Displaystyle s_ {i}}$ ${\ Displaystyle t_ {i}}$ ${\ Displaystyle D_ {i}}$ ${\ Displaystyle D _ {\ text {i}}}$ ${\ Displaystyle s_ {i}}$ ${\ Displaystyle t_ {i}}$ Algoritmo de Ford-Fulkerson , el flujo máximo y el corte mínimo son siempre iguales en un problema de flujo de 1 producto.

En un problema de flujo de múltiples productos básicos , el flujo máximo es el valor máximo de $f$ , donde $f$ es la fracción común de cada producto que se enruta, de modo que las unidades del producto $i$ se pueden enrutar simultáneamente para cada $i$ sin violar ninguna restricción de capacidad.min-cut es el mínimo de todos los cortes de la relación entre la capacidad del corte y la demanda del corte. El flujo máximo siempre está delimitado por el corte mínimo para un problema de flujo de múltiples productos básicos. ${\ Displaystyle fD _ {\ text {i}}}$ ${\ Displaystyle \ varphi}$

En un problema de flujo uniforme de múltiples productos básicos, hay un producto para cada par de nodos y la demanda de cada producto es la misma. (Sin pérdida de generalidad, la demanda de cada producto se establece en uno). La red y las capacidades subyacentes son arbitrarias. ^[1]

En un problema de flujo de productos múltiples de productos, hay un peso no negativo para cada nodo en el gráfico . La demanda del bien entre los nodos $u$ y $v$ es el producto de los pesos del nodo $u$ y del nodo $v$ . El problema del flujo uniforme de productos múltiples es un caso especial del problema del flujo de productos múltiples para el que el peso se establece en 1 para todos los nodos . ^[1] ${\ Displaystyle v \ in V}$ ${\ Displaystyle G = (V, E)}$ ${\ Displaystyle u \ in V}$

En general, el problema dual de un flujo de productos múltiples para un gráfico $G$ es el problema de distribuir una cantidad fija de peso (donde los pesos se pueden considerar como distancias) a los bordes de $G de$ manera que se maximice la distancia acumulada entre la fuente y el sumidero. pares. ^[1]