Teorema del flujo máximo y el corte mínimo

Una red consta de

• un grafo dirigido finito G = ( V , E ) , donde V denota el conjunto finito de vértices y E ⊆ V × V es el conjunto de aristas dirigidas;
• una fuente s ∈ V y un sumidero t ∈ V ;
• una función de capacidad , que es una función de mapeo${\displaystyle c:E\to \mathbb {R} ^{+}}$denotado por c _uv o c ( u , v ) para ( u , v ) ∈ E . Representa la cantidad máxima de flujo que puede pasar a través de una arista.

Un flujo a través de una red es un mapeo${\displaystyle f:E\to \mathbb {R} ^{+}}$denotado por${\displaystyle f_{uv}}$o${\displaystyle f(u,v)}$, sujeto a las dos restricciones siguientes:

1. Restricción de capacidad : Para cada arista${\displaystyle (u,v)\in E}$,${\displaystyle f_{uv}\leq c_{uv}.}$
2. Conservación de flujos : Para cada vértice${\displaystyle v}$aparte de${\displaystyle s}$y${\displaystyle t}$(es decir, la fuente y el sumidero, respectivamente), se cumple la siguiente igualdad:${\displaystyle \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.}$

Un flujo puede visualizarse como el movimiento físico de un fluido a través de la red, siguiendo la dirección de cada arista. La restricción de capacidad establece que el volumen que fluye a través de cada arista por unidad de tiempo es menor o igual a la capacidad máxima de la arista, y la restricción de conservación establece que la cantidad que entra en cada vértice es igual a la cantidad que sale de cada vértice, excepto en los vértices de origen y destino.

El valor de un flujo se define por

${\displaystyle |f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},}$

mientras que lo anterior${\displaystyle s}$es la fuente y${\displaystyle t}$es el sumidero de la red. En la analogía de fluidos, representa la cantidad de fluido que ingresa a la red en la fuente. Debido al axioma de conservación de flujos, esto equivale a la cantidad de flujo que sale de la red en el sumidero.

El problema del flujo máximo consiste en determinar el mayor flujo posible en una red determinada.

Problema del flujo máximo. Maximizar${\displaystyle |f|}$, es decir, dirigir la mayor cantidad de flujo posible desde${\displaystyle s}$a${\displaystyle t}$.

La otra mitad del teorema del flujo máximo y el corte mínimo se refiere a un aspecto diferente de una red: la colección de cortes. Un corte s-t C = ( S , T ) es una partición de V tal que s ∈ S y t ∈ T. Es decir, un corte s - t es una división de los vértices de la red en dos partes, con la fuente en una parte y el sumidero en la otra. El conjunto de cortes${\displaystyle X_{C}}$de un corte C es el conjunto de aristas que conectan la parte de origen del corte con la parte de destino:

${\displaystyle X_{C}:=\{(u,v)\in E\$ :\ u\in S,v\in T\}=(S\times T)\cap E.}

Por lo tanto, si se eliminan todas las aristas del conjunto de corte de C , entonces no es posible ningún flujo positivo, porque no hay ningún camino en el grafo resultante desde el origen hasta el destino.

La capacidad de un corte st es la suma de las capacidades de las aristas en su conjunto de corte,

${\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},}$

dónde${\displaystyle d_{ij}=1}$si${\displaystyle i\in S}$y${\displaystyle j\in T}$,${\displaystyle 0}$de lo contrario.

Normalmente, un gráfico presenta muchos cortes, pero los cortes con menor ponderación suelen ser más difíciles de encontrar.

Problema de corte st mínimo. Minimizar c ( S , T ) , es decir, determinar S y T de manera que la capacidad del corte st sea mínima.

En la situación descrita, se puede demostrar que el valor de cualquier flujo a través de una red es menor o igual a la capacidad de cualquier corte st , y que, además, existe un flujo con valor máximo y un corte con capacidad mínima. El teorema principal relaciona el valor máximo del flujo con la capacidad mínima del corte de la red.

Teorema del flujo máximo y el corte mínimo. El valor máximo de un flujo st es igual a la capacidad mínima sobre todos los cortes st.

El problema del flujo máximo puede formularse como la maximización de la corriente eléctrica a través de una red compuesta por elementos resistivos no lineales. ^{[ 4 ]} En esta formulación, el límite de la corriente I _entre los terminales de entrada de la red eléctrica a medida que la tensión de entrada V _se aproxima${\displaystyle \infty }$, es igual al peso del conjunto de corte de peso mínimo.

${\displaystyle \lim _{V_{\text{in}}\to \infty }(I_{in})=\min _{X_{C}}\sum _{(u,v)\in X_{C}}c_{uv}}$

Además de la capacidad de las aristas, considérese que hay capacidad en cada vértice, es decir, una asignación.${\displaystyle c:V\to \mathbb {R} ^{+}}$denotado por c ( v ) , de modo que el flujo f debe satisfacer no solo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad de vértice.

${\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).}$

En otras palabras, el flujo que pasa por un vértice no puede exceder su capacidad. Definimos un corte st como el conjunto de vértices y aristas tales que, para cualquier camino de s a t , dicho camino contiene un elemento del corte. En este caso, la capacidad del corte es la suma de la capacidad de cada arista y vértice que lo compone.

En esta nueva definición, el teorema generalizado de flujo máximo y corte mínimo establece que el valor máximo de un flujo st es igual a la capacidad mínima de un corte st en el nuevo sentido.

En el problema de caminos disjuntos por aristas no dirigidos, se nos da un grafo no dirigido G = ( V , E ) y dos vértices s y t , y tenemos que encontrar el número máximo de caminos st disjuntos por aristas en G .

El teorema de Menger establece que el número máximo de caminos st disjuntos en aristas en un grafo no dirigido es igual al número mínimo de aristas en un conjunto de corte st.

En el problema de selección de proyectos, existen n proyectos y m máquinas. Cada proyecto p _i genera ingresos r ( p _i ) y cada máquina q _j tiene un costo de adquisición c ( q _j ) . Queremos seleccionar un subconjunto de proyectos y adquirir un subconjunto de máquinas para maximizar la ganancia total (ingresos de los proyectos seleccionados menos el costo de las máquinas adquiridas). Debemos cumplir con la siguiente restricción: cada proyecto especifica un conjunto de máquinas que deben adquirirse si se selecciona dicho proyecto. (Cada máquina, una vez adquirida, puede ser utilizada por cualquier proyecto seleccionado).

Para resolver el problema, sea P el conjunto de proyectos no seleccionados y Q el conjunto de máquinas compradas, entonces el problema se puede formular como:

${\displaystyle \max\{g\}=\sum _{i}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j}).}$

Dado que el primer término no depende de la elección de P y Q , este problema de maximización puede formularse como un problema de minimización, es decir,

${\displaystyle \min\{g'\}=\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).}$

El problema de minimización anterior puede formularse como un problema de corte mínimo mediante la construcción de una red, donde la fuente está conectada a los proyectos con capacidad r ( p _i ) , y el sumidero está conectado a las máquinas con capacidad c ( q _j ) . Se agrega una arista ( p _i , q _j ) con capacidad infinita si el proyecto p _i requiere la máquina q _j . El conjunto de corte st representa los proyectos y las máquinas en P y Q respectivamente. Mediante el teorema de flujo máximo y corte mínimo, se puede resolver el problema como un problema de flujo máximo .

La figura de la derecha presenta una formulación en red del siguiente problema de selección de proyectos:

La capacidad mínima de un st cut es 250 y la suma de los ingresos de cada proyecto es 450; por lo tanto, la ganancia máxima g es 450 − 250 = 200, al seleccionar los proyectos p ₂ y p ₃ .

La idea es canalizar las ganancias de cada proyecto a través de las máquinas que lo componen. Si una máquina no puede llenar el flujo, su retorno es menor que su costo, y el algoritmo de corte mínimo considerará más económico recortar la ganancia del proyecto que el costo de la máquina.

En el problema de segmentación de imágenes , hay n píxeles. A cada píxel i se le puede asignar un valor de primer plano f _i o un valor de fondo b _i . Existe una penalización de p _ij si los píxeles i y j son adyacentes y tienen asignaciones diferentes. El problema consiste en asignar píxeles a primer plano o fondo de tal manera que la suma de sus valores menos las penalizaciones sea máxima.

Sea P el conjunto de píxeles asignados al primer plano y Q el conjunto de puntos asignados al fondo, entonces el problema se puede formular como:

${\displaystyle \max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.}$

Este problema de maximización puede formularse como un problema de minimización, es decir,

${\displaystyle \min\{g'\}=\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.}$

El problema de minimización anterior se puede formular como un problema de corte mínimo mediante la construcción de una red donde la fuente (nodo naranja) está conectada a todos los píxeles con capacidad f _i , y el sumidero (nodo púrpura) está conectado a todos los píxeles con capacidad b _i . Se agregan dos aristas ( i, j ) y ( j, i ) con capacidad p _ij entre dos píxeles adyacentes. El conjunto de corte st representa entonces los píxeles asignados al primer plano en P y los píxeles asignados al fondo en Q .