Algoritmo de empuje de preflujo

El algoritmo de empuje de preflujo resuelve el problema de encontrar el flujo máximo en la red de transporte . El algoritmo no es un caso especial del algoritmo de Ford-Fulkerson . Implementado sin mejoras especiales, el algoritmo se ejecuta en el tiempo . Algunas mejoras aceleran aún más el algoritmo: la regla de selección de vértices "elevar al principio" - hasta , la selección del vértice activo más alto - hasta , la implementación utilizando las estructuras de datos de Seanor y Tarjan - hasta . Publicado por primera vez en 1986 por Andrew W. Goldberg y Tarjan. [1] . $O(V^{2}E)$ ${\ estilo de visualización O (V ^ {3})}$ $O(V^{2}{\sqrt {E)))$ $O(VE\log(V^{2}/E))$

Descripción del algoritmo

Definiciones y notación

En este artículo, llamamos a un hijo de un vértice u cualquier vértice v tal que la red residual contenga una arista (u, v).

Denotamos los conjuntos de vértices y aristas de la red por y , y sus números por V y E. ${\mathbf{V}}$ $\mathbf {E}$

El algoritmo usa preflow , una función con las siguientes propiedades para cualquier vértice y : $\ f:V\times V\rightarrow {\mathbb {R}}$ $\u$ $\v$

Limitación de ancho de banda. La transmisión no puede exceder el ancho de banda: $\f(u,v)\leq c(u,v).$
Antisimetría. El flujo de a debe ser el opuesto del flujo de a : $\u$ $\v$ $\v$ $\u$ $\f(u,v)=-f(v,u).$
No negatividad del exceso de flujo: para todos excepto fuente y sumidero. ${\ estilo de visualización \ \ suma _ {w \ en V} f (w, u) \ geq 0}$ $\u\en V$

Las dos primeras propiedades son las mismas que las de un flujo, la tercera es un debilitamiento de la propiedad de persistencia del flujo. La suma contenida en esta propiedad se llama exceso de flujo (exceso) y se denota por . De acuerdo con esta propiedad, el exceso de flujo no es negativo para todos los vértices excepto la fuente y el sumidero. ${\ estilo de visualización \ \ suma _ {w \ en V} f (w, u)}$ ${\ Displaystyle e_ {u}}$

Llamamos desbordamiento a un vértice si no es ni una fuente ni un sumidero, y el exceso de flujo hacia ese vértice es estrictamente positivo. Es fácil ver que un preflujo es un flujo si y solo si no hay vértices de desbordamiento.

Variables

El algoritmo almacena los siguientes datos:

preflujo f
exceso de flujo para cada vértice $e_{u}\$
un número entero no negativo asignado a cada vértice, llamado altura . La altura del vértice u se denota por . $h_{u}\$

Inicialización

Inicialmente, el flujo previo es igual a la capacidad de todos los bordes que salen de la fuente y es opuesto para los pares de vértices inversos:

f(s,u)=c(s,u)\

f(u,s)=-c(s,u)\

Para los pares de vértices restantes, el preflujo es igual a cero.

La altura inicial es V para el origen y 0 para todos los demás vértices.

Operaciones

El algoritmo utiliza dos operaciones: empujar (push) y levantar (relabel).

Empujando

Empujar desde el vértice u al vértice v es posible bajo las siguientes condiciones:

la parte superior está llena
la red residual contiene el borde (u, v) (en otras palabras, v es un descendiente de u)
v debajo de ti: $h_{u}>h_{v}\$

Empujando es que el flujo se incrementa en una cantidad ${\ estilo de visualización f (u, v)}$

\delta f(u,v)=\min(e_{u},c(u,v)-f(u,v))\

El exceso de flujo aumenta en la misma cantidad . $e_{v}\$

El flujo inverso y el exceso de flujo se reducen en la misma cantidad. ${\ estilo de visualización f (v, u) \ }$ $e_{u}\$

Empujar se llama saturar si . Después de un empujón de saturación , se vuelve igual a , como resultado de lo cual el borde (u, v) se excluye de la red residual. Con un empujón no saturado , por lo tanto, hace que el vértice u se descargue. $\delta f(u,v)=c(u,v)-f(u,v)\$ ${\ estilo de visualización f (u, v) \ }$ ${\ estilo de visualización c (u, v) \ }$ ${\ estilo de visualización \ delta f (u, v) = e_ {u} \ }$

Subida

El levantamiento del vértice u es posible bajo las siguientes condiciones:

la parte superior está llena
no hay descendientes de ti debajo de ti

El levantamiento significa que de todos los descendientes de u, se selecciona el vértice v con la altura mínima, después de lo cual la altura del vértice u se vuelve igual a . $h_{v}+1$

Algoritmo

Inicializar preflujo, flujos redundantes y alturas
Mientras sea posible empujar o levantar, realice cualquier operación posible.

Propiedades del algoritmo

Prueba de caudal máximo

Probemos que si el algoritmo alguna vez termina, en ese momento el preflujo será el flujo máximo. En el camino, probamos otros lemas que son útiles para lo que sigue.

Lema 1 . Elevar cualquier vértice aumenta su altura.
prueba _ Antes de ascender, la cima no es más alta que la más baja de sus descendientes. Después de levantarse, ella es más alta que él. La altura del niño no ha cambiado. En consecuencia, la altura de la parte superior que se levanta ha aumentado.

Lema 2 . La altura de cualquier vértice nunca decrece.
prueba _ Empujar no cambia la altura de los vértices. Elevar aumenta la altura del vértice que se eleva y no cambia la altura de otros vértices.

Lema 3 . Las alturas de fuente y sumidero siempre permanecen iguales a V y 0, respectivamente.
prueba _ La fuente y el sumidero, por definición, no pueden desbordarse y, por lo tanto, nunca se elevan. Ni elevar otros vértices ni empujar afecta la altura de la fuente o sumidero. Por lo tanto, sus alturas siempre son las mismas que en el momento de la inicialización, lo que debía probarse.

Lema 4 . f siempre satisface las propiedades de preflujo.
prueba _ Lo demostramos por inducción sobre el número de operaciones realizadas. Necesitamos probar que después de la inicialización, f satisface las propiedades del preflujo, y también que si f satisface las propiedades del preflujo antes de la operación de empujar o levantar, las satisfará después.

Inicialización . Se demuestra mediante una comprobación trivial de las propiedades del preflujo.
empujando _ Esto también se demuestra mediante una comprobación trivial de las propiedades del preflujo.
Levántate _ No afecta a los hilos en absoluto.

Lema 5 ( propiedad de la altura ) . Para cualquier borde de la red residual (u, v), la desigualdad

h_{u}\leq h_{v}+1\

prueba _ Probamos por inducción sobre el número de operaciones realizadas de forma similar al lema anterior.

Inicialización . Después de la inicialización, la altura de la fuente V, cualquier otro vértice es 0. Por lo tanto, la desigualdad puede violarse solo si , . Pero no existen tales bordes en la red residual. De hecho, si el gráfico contiene una arista (s, v), entonces , y la capacidad residual de la arista es cero. Si el gráfico no contiene tal arista, entonces y , y nuevamente, la capacidad residual de la arista es cero. $h_{u}\leq h_{v}+1$ $u=s\$ $v\neq s\$ ${\ Displaystyle f (s, v) = c (s, v)}$ ${\ estilo de visualización f (s, v) = 0}$ ${\ estilo de visualización c (s, v) = 0}$
empujando _ No afecta las alturas de los vértices, pero puede crear un borde (v, u) en la red residual y/o excluir un borde (u, v) de ella.
- Crea un borde (v, u) . Empujar es posible sólo si , de donde sigue . Esto significa que la condición se cumple para el borde recién creado. $h_{v}<h_{u}\$ $h_{v}\leq h_{u}+1\$
- Eliminación de aristas (u, v) . Cancela una de las condiciones de la propiedad height, por lo que no detiene su ejecución.
Levántate _ Considere la desigualdad para cualquier par de vértices. Antes de levantarlo se hace. Si u es un vértice que no se puede levantar, entonces el levantamiento no cambia la altura y no disminuye , lo que significa que la desigualdad se mantendrá después del levantamiento. Si u es un vértice escalable, entonces sea w el más bajo de sus descendientes. Luego, después de levantar , lo que se requiere para ser probado. $h_{u}\leq h_{v}+1\$ $h_{u}\$ $h_{v}\$ $h_{u}=h_{w}+1\leq h_{v}+1\$

Lema 6 . Si el vértice w en la red residual es accesible desde el vértice u, entonces . prueba _ Considere el camino más corto de u a w. No contiene ciclos, por lo que su duración es como máximo . Pero por la propiedad de la altura, en cada borde de este camino, la altura decrece en no más de 1. Por lo tanto, en todo el camino decrece en no más de , lo que se requiere probar. $h_{u}-h_{w}<V\$
${\ estilo de visualización V-1}$ ${\ estilo de visualización V-1}$

Lema 7 . En la red residual, el sumidero nunca es accesible desde la fuente.
prueba _ Que no sea así. Luego por el lema anterior . Pero por el Lema 3, . Contradicción. $h_{s}-h_{t}<V\$ $h_{s}-h_{t}=V-0=V\$

Lema 8 . Si el algoritmo alguna vez termina, en ese punto el preflujo será un hilo.
prueba _ Dado un vértice desbordado, siempre podemos empujar (si el vértice es más alto que al menos un niño) o levantar (de lo contrario). Dado que el algoritmo termina solo cuando no son posibles las operaciones, no hay vértices desbordados en este momento, lo que implica la afirmación del lema.

teorema _ Si el algoritmo alguna vez termina, en ese punto el preflujo será el flujo máximo.
prueba _ Por el Lema 8, el preflujo se convierte en un flujo. Por el Lema 7, en la red residual, el sumidero no será alcanzable desde la fuente, en otras palabras, no habrá camino de aumento. Por lo tanto, el caudal será máximo. [2]

El número máximo de operaciones de empujar y levantar

En esta sección, no solo probaremos que el algoritmo se completará en un tiempo finito, sino que también daremos un límite superior en el número máximo de operaciones de empujar y levantar.

Lema 1 . El exceso de flujo al sumidero ( ) nunca disminuye. prueba _ Empujar de u a v reduce el exceso de flujo solo en u, mientras que empujar no afecta el exceso de flujo en absoluto. Por lo tanto, la única forma de disminuir es empujando desde el fregadero hasta otro vértice. Pero empujar solo es posible desde vértices desbordados, y el sumidero no puede desbordarse por definición. Entonces es imposible de reducir. $e_{t}$
$e_{t}$ $e_{t}$

Lema 2 . El exceso de flujo al fregadero ( ) siempre es no negativo. prueba _ Inmediatamente después de la inicialización, es igual a , por lo tanto, no es negativo. En el futuro, no disminuye, por lo tanto, permanece no negativo. $e_{t}$
${\ estilo de visualización c (s, t)}$

Lema 3 . En la red residual, la fuente siempre es accesible desde cualquier vértice lleno de gente.
prueba _ Sea inalcanzable la fuente s desde algún vértice u. Probemos que u no se desborda. Sean U, U' los conjuntos de vértices alcanzables e inalcanzables desde u en la red residual, respectivamente. Por suposición, . Considere cualquier par de vértices , . No hay arista (v,w) en la red residual, de lo contrario sería posible llegar a v desde u y luego a lo largo de esta arista w, lo que contradice . Por otro lado, si , entonces la capacidad residual es positiva, por lo que debe haber tal borde. Entonces, de donde . Ahora vamos a sumar los flujos en exceso a todos los vértices de U: $s\notin U$ ${\ estilo de visualización v \ en U}$ ${\ estilo de visualización con \ en U'}$ ${\ estilo de visualización con \ en U'}$ ${\ estilo de visualización f (v, w) <0 \}$ $c(v,w)-f(v,w)\$ $f(v,w)\geq 0\$ $f(w,v)\leq 0\$

\sum_{v\in U}e_{v}=\sum_{v\in U}\sum_{w\in V}f(w,v)=\sum_{v\in U} }\sum_{w\in U}f(w,v)+\sum_{v\in U}\sum_{w\in U'}f(w,v)

La primera de las dos sumas del lado derecho es igual a cero, porque para cada par de vértices relevante (v,w) tiene dos términos f(v,w) y f(w,v) cuya suma es igual a cero . El segundo es no positivo, ya que todos sus términos son no positivos. Medio,

\sum _{v\in U}e_{v}\leq 0

Por otro lado, cada término en la suma es no negativo: $\sum _{v\in U}e_{v}$

si v no es ni una fuente ni un sumidero, entonces por la tercera propiedad de los preflujos $e_{v}\geq 0$
no hay fuente, porque $s\notin U$
$e_{t}\geq 0$ por el lema anterior

Como la suma de los términos no negativos no es positiva, se sigue que todos sus términos son iguales a cero. En particular, , es decir, u no se desborda, lo que se iba a demostrar. $e_{u}=0\$

Lema 4 . La altura de cualquier vértice es siempre menor que 2V.
prueba _ Considere algún vértice u. La única forma de cambiar la altura de un vértice es levantar ese vértice. Por lo tanto, si el vértice u nunca ha sido elevado, su altura sigue siendo la misma que tenía después de la inicialización, es decir, 0 o V, y el lema queda probado. De lo contrario, su altura se mantuvo igual a la que se convirtió como resultado de la última elevación. Antes del último ascenso, u estaba desbordado, lo que significa que en la red residual, la fuente s era accesible desde ella. Después del ascenso, el camino de u a s en la red residual se conserva porque el ascenso no afecta la red residual. Así, por el Lema 6 de la sección anterior, , de donde , lo que había que probar. $h_{u}-h_{s}<V$ $h_{u}2V$

teorema _ Durante todo el tiempo de funcionamiento del algoritmo, no puede haber más de . prueba _ Levantar un vértice aumenta su altura en al menos 1. La altura inicial de cada vértice no es inferior a 0, la final, según el lema anterior, no es superior a 2V-1. La altura del vértice no se puede reducir. Esto significa que cada vértice no puede soportar más de 2V-1 subidas. En total, no puede levantar más de V-2 vértices (todos menos s y t). Esto implica la afirmación del teorema. ${\ estilo de visualización (2V-1) (V-2)}$

teorema _ Durante todo el tiempo de funcionamiento del algoritmo, no puede haber más de . prueba _ Considere dos empujones de saturación sucesivos de u a v. El primero de ellos excluye la arista (u, v) de la red residual, para cuando se ejecuta la segunda, esta arista vuelve a aparecer. Entonces, entre estos dos empujes, se realiza un empuje de v a u, que es la única forma de restaurar el borde. Durante el primer empujón de saturación , mientras empuja de v a u, por el contrario, . Considerando que las alturas no pueden disminuir, obtenemos que la altura ha aumentado al menos 2. Como esto ocurre entre cada dos empujones de saturación sucesivos de u a v, y la altura de cualquier vértice no puede aumentar más de 2V-1 (de 0 a 2V-1), el número de empujones de u a v no excede a V. En total, hay 2E pares de vértices adecuados para empujar (todas las aristas y sus inversos). Por lo tanto, no puede haber más empujones de saturación que 2VE. ${\ estilo de visualización 2VE}$
${\ Displaystyle h_ {u}> h_ {v}}$ ${\displaystyle h_{u}<h_{v))$ $h_{v}$

Finalmente, para encontrar un límite superior en el número de empujones no saturados, usamos la suma de las alturas de todos los vértices desbordados como una función potencial. Denotemos esta suma por Φ. Un empujón no saturado de u a v no cambia las alturas, pero hace que u pase de lleno a vacío, y puede convertir v de vacío a lleno; no afecta el estado de otros vértices. Por lo tanto, Φ disminuye en al menos . El empuje solo es posible si , por lo tanto, el empuje no saturado reduce Φ en al menos 1. Inicialmente Φ=0, pero Φ nunca puede volverse negativo. Esto significa que el algoritmo solo puede realizar tantos impulsos no saturados como las otras operaciones aumentan Φ. Raise aumenta Φ en no más de 2V-1, y Saturating Push aumenta Φ en no más de 2V-1. Por lo tanto, el número total de tales impulsos es como máximo , o . ${\displaystyle h_{u}-h_{v))$ ${\ Displaystyle h_ {u}> h_ {v}}$ ${\ estilo de visualización (2V-1)^{2}(V-2)+2VE(2V-1)}$ $O(V^{2}(V+E))$

Dado que los vértices aislados (que no son incidentes en ningún borde de la red original) no afectan las operaciones de empuje o elevación de ninguna manera, podemos excluirlos mentalmente para estimar el número de operaciones, después de lo cual . Por lo tanto, el número de empujones no saturados es . Agregando como máximo los empujones de saturación aquí, obtenemos que el número total de empujones también es . $V\leq 2E$ $O(V^{2}E)$ ${\ estilo de visualización 2VE}$ $O(V^{2}E)$

Implementación

Almacenamos un conjunto de vértices desbordados, y para cada vértice, dos conjuntos de descendientes: con no menos altura y con menos altura. Almacenamos todos estos conjuntos simplemente como matrices (en términos de C++ - vectores) de elementos.

Determinar qué acción tomar:
- si el conjunto de vértices desbordados está vacío, deténgase
- copiar su último elemento a usted
- si no tienes hijos de menor estatura, llámame para que te levantes
- de lo contrario, copie el último elemento secundario en v y llame a push de u a v
Empujando de u a v
- cambie f(u, v), f(v, u), e(u), e(v), después de guardar sus valores anteriores
- si es necesario, excluya u del conjunto de vértices desbordados
- agregue v a este conjunto si es necesario
- si es necesario, excluya v del conjunto de descendientes de u
- si es necesario, agregue u al conjunto de hijos de v con altura no menor
subir arriba
- mira las alturas de todos los descendientes y encuentra el mínimo de ellos
- cambiar la altura del vértice u
- miramos a través de todos los descendientes con una altura no menor, y transferimos algunos de ellos al conjunto de descendientes con una altura más baja
- miramos a través de todos los vecinos del vértice u (las listas de vecinos deben prepararse durante la inicialización) y, si es necesario, transferimos u al conjunto de descendientes con una altura no menor.

La determinación de la acción requerida y el empuje se realizan en tiempo constante (tenga en cuenta que al empujar siempre se excluye el último elemento del conjunto). Por lo tanto, todas las definiciones de la acción y el empuje deseados requieren operaciones. $O(V^{2}E)\$

Para encontrar el tiempo de subida, notamos que la transferencia del vértice u al conjunto de descendientes con altura no menor requiere su exclusión del conjunto de descendientes con una altura menor. Dado que los conjuntos de descendientes se almacenan como vectores, y eliminar un elemento de un vector requiere un número de operaciones proporcional a su longitud, dicha transferencia puede requerir operaciones. Esto significa que realizar traslaciones para todos los vecinos requiere operaciones, donde es el grado del vértice u. El resto de acciones realizadas durante el izaje requieren menos operaciones, por lo que el izaje requiere operaciones. Un vértice puede resistir el levantamiento, por lo tanto, todos sus levantamientos requieren operaciones, y todos los levantamientos de todos los vértices requieren operaciones. $O(V)\$ $O(d_{u}V)\$ $d_{u}\$ $O(d_{u}V)\$ ${\ estilo de visualización 2V-1 \ }$ $O(d_{u}V^{2})\$ $O(\sum_{u}d_{u}V^{2})=O(V^{2}E)\$

Por lo tanto, la implementación del algoritmo requiere operaciones. $O(V^{2}E)\$

Algoritmo "subir al principio"

El algoritmo de reetiquetado al frente es una implementación más eficiente del algoritmo de inserción de flujo previo que la descrita anteriormente. El tiempo de funcionamiento es . ${\ estilo de visualización O (V ^ {3})}$

Aristas válidas

El algoritmo utiliza el concepto de aristas admisibles . Una arista (u, v) se considera admisible si se cumplen dos condiciones:

${\ estilo de visualización f (u, v) <c (u, v) \ }$ , o de manera equivalente, el borde (u, v) está presente en la red residual.
$h_{u}=h_{v}+1\$

Nótese que, teniendo en cuenta la propiedad de la altura, estas condiciones coinciden con las dos últimas condiciones para la aplicabilidad de la operación de empujar a los bordes. Como consecuencia,

El empuje se realiza solo a lo largo de los bordes admisibles.

Además, la admisibilidad del levantamiento, teniendo en cuenta la propiedad de la altura, se puede formular de la siguiente manera

El levantamiento es admisible si y solo si el vértice que se levanta está desbordado y no hay bordes admisibles que provengan de él.

Además, se pueden probar dos propiedades más de los bordes admisibles.

Propiedad 1. Empujar no crea nuevos bordes válidos.
Prueba. Supongamos que algún empujón hizo admisible el borde (u, v). La admisibilidad de un borde (u, v) está completamente determinada por 4 parámetros: las alturas de los vértices u y v, el flujo a lo largo del borde y su capacidad. Las alturas de los vértices y las capacidades de los bordes no se ven afectadas por ningún empuje. Esto significa que afectó el flujo f(u, v). Esto solo se puede hacer empujando a lo largo del borde (u, v) o (v, u). Pero empujar a lo largo del borde (u, v) requiere que ya sea admisible antes de empujar, lo que contradice la suposición. Empujar a lo largo del borde (v, u) requiere, en particular, que u esté por debajo de v. Dado que empujar no afecta las alturas, u será menor que v después de empujar, lo que viola la segunda condición de admisibilidad.

Propiedad 2. Después de levantar el vértice v, todas las aristas incluidas en v serán inválidas.
Prueba. Consideremos cualquier borde (u, v) y demostremos que después de levantarlo será inválido.

Si antes del ascenso el borde estaba presente en la red residual, entonces por la propiedad de la altura . El ascensor aumenta la altura del vértice v, por lo tanto, después de él , lo que viola la segunda propiedad de admisibilidad. $h_{u}\leq h_{v}+1$ $h_{u}<h_{v}+1$
Si un borde estaba ausente en la red residual antes del levantamiento, también estará ausente después del levantamiento, porque el levantamiento no afecta los flujos. Esto significa que se violará la primera condición de admisibilidad.

Valores almacenados

Además del preflujo y las alturas, el algoritmo almacena lo siguiente:

Para cada vértice v hay una lista de sus vecinos . La lista contiene todos los vértices w tales que la red contiene una arista (v,w) o una arista (w,v). El orden es arbitrario. Las listas de vecinos se construyen una vez al comienzo del algoritmo y no cambian más. ${\ estilo de visualización N [v]}$
Para cada vértice, v es un puntero a uno de los elementos de la lista de vecinos (en términos de C++ , un iterador). Al principio apunta al primer elemento de la lista. $actual[v]$
Lista L de todos los vértices excepto fuente y sumidero. Inicialmente contiene vértices en orden aleatorio. En el futuro, los vértices se pueden mover, pero no excluir ni agregar a la lista.
Apúntelo a uno de los elementos de la lista L (en términos de C++ , un iterador). Al principio apunta al primer elemento de la lista.

Descarga

En esta sección, describiremos una función llamada descarga de vértice . El espaciado se aplica solo a los vértices abarrotados.

Descripción

La descarga del vértice u se realiza de la siguiente manera:

Paso 1. Mientras el vértice u está lleno, siga los pasos 2-4. Paso 2. Si la corriente ha ido más allá del final de la lista, eleve el vértice u y regrese la corriente al principio de la lista. Paso 3. De lo contrario, si se permite pasar de u a actual[u], hágalo. Paso 4. De lo contrario, avance el elemento actual 1 hacia adelante. Propiedades

Lema 1 . Después de cada iteración del bucle, si la función no se ha detenido, el vértice u se desbordará.
prueba _ Sigue desde el registro en el paso 1.

Lema 2 . Después de cada iteración del ciclo, el borde (u, actual[u]) no es válido, no existe o la función se detendrá. Aquí actual es el valor del puntero al inicio de la iteración .
prueba _ Si se cumplió la condición del paso 2, el borde no existe. De lo contrario, si no se cumplió la condición del paso 3, el borde no era válido; dado que el empuje no crea nuevos bordes válidos, sigue siendo inválido. Finalmente, si el empuje se realizó en el paso 3, fue saturado o no saturado. En el primer caso, el borde (u, v) ha desaparecido de la red residual, lo que significa que se viola la primera condición de admisibilidad para él. En el segundo caso, el vértice dejó de desbordarse, después de lo cual la función se detuvo en el paso 1.

Lema 3 . Cuando se cumple la condición del paso 2, no se permite ningún borde que salga de u.
prueba _ Considere cualquiera de tales aristas (u, v). Si el vértice v no es adyacente al vértice u, entonces no hay borde en la red residual, por lo que se viola la primera condición de admisibilidad. De lo contrario, el vértice se consideró en el paso 3. Considere la última vez que esto sucedió. Inmediatamente después de esto, la arista (u, v), por el lema anterior, quedó invalidada. Además, no se pueden realizar operaciones en la función, excepto empujar a lo largo de otros bordes que emanan de u. Tales empujones no podrían, por la primera propiedad de admisibilidad, hacer que el borde (u, v) sea admisible nuevamente.

propiedad 1 . Empujar y levantar se realizan solo cuando están permitidos.
prueba _ La admisibilidad de cada impulso se comprueba explícitamente. La admisibilidad del levantamiento está garantizada por el hecho de que en el paso 2 el vértice u estará desbordado por el Lema 1, y también por el hecho de que no emanan aristas admisibles de él por el Lema 3.

propiedad 2 . Después de que termina la función, el vértice u no se desborda.
prueba _ La función solo puede detenerse en el paso 1. La parada ocurre solo si el vértice u no se desborda.

Descripción del algoritmo

Además de la secuencia previa y las alturas, el algoritmo "elevar al principio" almacena una lista de vértices L y un puntero a uno de sus elementos (en términos de C++, un iterador) it .

Inicialización:
- Inicialice los flujos y las alturas como en el algoritmo de inserción de preflujo.
- Si no hay vértices además de la fuente y el sumidero, deténgase; la tarea esta resuelta.
- Cree listas de vecinos de todos los vértices y establezca iteradores al comienzo de las listas.
- Escriba en L una lista de todos los vértices, excepto la fuente y el sumidero, en un orden arbitrario.
- apunta al principio de la lista .
Siempre y cuando apunte a algún principio de la lista:
- Desplaza el vértice al que apunta .
- Si el vértice ha cambiado de altura durante la descarga, reorganícelo e itérelo al principio de la lista (para que siga apuntándolo).
- Avance el iterador una posición hacia adelante.

Propiedades

Un tipo topológico de un dígrafo (V,E) es una lista de algunos de sus vértices, ordenados de tal manera que para cualquier borde , u está en la lista antes de v. ${\ estilo de visualización (u, v) \ en E}$

Lema 1. Después de cada iteración del bucle exterior, la lista L es una especie topológica del gráfico de aristas admisibles (ATGGR).
Prueba. Inducción sobre el número de iteraciones del bucle exterior.
Base. Después de la inicialización, la altura de la fuente es igual a V, todos los demás vértices son 0. Al mismo tiempo , porque hay al menos 2 vértices: fuente y sumidero. Por lo tanto, para cualquier par de vértices, se viola la segunda condición de admisibilidad y no hay aristas admisibles en absoluto. Por lo tanto, cualquier lista de vértices es un TSGDR. Paso. Veamos la v. $V\geq 2$

Si no estaba elevado, el orden de los vértices no cambiaba. Antes de verlo, la lista era TSGDR. Durante el escaneo, solo se realizaron operaciones de inserción, que no crean nuevos bordes válidos. Por lo tanto, la lista permaneció TSGDR.
Si se recogió, entonces se movió a la parte superior de la lista. Probemos que todas las aristas admisibles satisfacen la condición de clasificación topológica.
- Saliente de v: debe satisfacer la condición de clasificación topológica en cualquier caso, ya que v está al principio de la lista.
- Incluido en v: no hay ninguno. En efecto, por la propiedad de la altura, antes del último levantamiento, para cualquier borde de la red residual, . El alza aumentó , por tanto, después de que ya se realizó , lo que viola la segunda propiedad de admisibilidad. Por lo tanto, para cualquier vértice u, el borde inmediatamente después del ascenso no entró en la red residual o violó la segunda propiedad de admisibilidad. En ambos casos no fue válido. Desde entonces, no se ha realizado ninguna operación, salvo quizás el empujón. Como hemos mostrado, los empujones no crean nuevos bordes válidos. $(u,v)$ $h_{u}\leq h_{v}+1$ $h_{v}$ $h_{u}<h_{v}+1$ $(u,v)$
- No incidente v: durante la iteración, no cambió su admisibilidad ni el orden relativo de los vértices distintos de v. Por lo tanto, todos estos bordes seguirán satisfaciendo la condición de clasificación topológica.

Lema 2. Después de cada iteración del ciclo externo, el vértice escaneado y todos los vértices a su izquierda en la lista no se desbordan.
Prueba. Inducción sobre el número de iteraciones del bucle exterior.
Base. Después de la primera iteración, la propiedad de espaciado no desborda el vértice escaneado y no hay vértices a la izquierda.
Paso. Veamos la v. Ella misma no está desbordada por la propiedad de la descarga. Si se levanta y, por lo tanto, se mueve al principio de la lista, entonces no hay vértices a la izquierda y el teorema está probado. De lo contrario, en esta iteración, solo se realizaron operaciones de empuje desde el vértice v a los vértices a los que conducen los bordes admisibles desde v. Dado que la operación de inserción no crea nuevos bordes válidos, todos estos bordes eran válidos antes del inicio de la iteración. Por lo tanto, según el lema anterior, todos los vértices a los que se realizó el empuje estaban a la derecha de v en la lista. Por lo tanto, los vértices a la izquierda de v en la lista no podrían desbordarse en esta iteración. Pero por la hipótesis de la inducción, tampoco estaban superpoblados antes. El teorema ha sido probado.

Lema 3. Después de completar el algoritmo, ningún vértice se desborda.
Prueba. Para completar el algoritmo, debemos fijarnos en el último vértice de la lista L. Por el lema anterior, después de eso, ningún vértice de la lista L se desborda. Pero la lista L contiene todos los vértices excepto el origen y el sumidero, y el origen y el sumidero no pueden desbordarse por definición.

Propiedad. El algoritmo de elevación al frente (PHA) es un caso especial del algoritmo de empuje de preflujo (PFP).
Prueba. La inicialización de alturas y preflujo en el ALP es la misma que en el APS. Los cambios de altitud y flujo previo en el ALP ocurren solo al activar una descarga, que a su vez solo realiza operaciones legítimas de empuje y elevación. Finalmente, al final del APN, ningún vértice se desborda, por lo que las operaciones de empujar o levantar no son posibles.

Horario de apertura

Estimemos el número de veces que se realizan diferentes acciones y su tiempo total de ejecución.

Altas

Con cada descarga sin levantar, se desplaza una posición a la derecha. La lista L contiene V-2 vértices, por lo tanto, más de V-2 descargas seguidas sin levantarse es imposible. El número de subidas , por tanto, el número de altas . $O(V^{2})$ ${\ estilo de visualización O (V ^ {3})}$

La llamada de descarga en sí y los costos asociados (avanzar el iterador, retroceder) toman un tiempo constante. Por lo tanto, el tiempo total para todas esas acciones es . ${\ estilo de visualización O (V ^ {3})}$

Escalada

Considere un vértice arbitrario u. Sea su grado. La cima no puede elevarse más de 2V-1 veces, y el tiempo empleado en cada ascenso es . Por lo tanto, el tiempo empleado en levantar todos los vértices es , o . ${\ Displaystyle d_ {u}}$ ${\ estilo de visualización O (d_ {u})}$ $O\left((2V-1)\sum_{u}d_{u}\right)$ $O(VE)$

Empujando

Los empujones de saturación, como probamos antes, no son más que O(VE).

El empuje que no satura hace que la parte superior se despeje, después de lo cual se detiene la descarga. Por tanto, no hay más empujones no saturados que llamadas de descarga, es decir, . ${\ estilo de visualización O (V ^ {3})}$

El tiempo de ejecución de una pulsación es constante. Esto significa que el tiempo total de ejecución de los impulsos es . ${\ estilo de visualización O (V ^ {3})}$

El iterador cambia la corriente

Considere un vértice arbitrario u. Sea su grado. Cada cambio de corriente[u] hace que el vértice se eleve. Ascensores totales no más de 2V-1. Por lo tanto, el número de cambios de iterador para todos los vértices es , o . ${\ Displaystyle d_ {u}}$ ${\ Displaystyle d_ {u}}$ $O\left((2V-1)\sum_{u}d_{u}\right)$ $O(VE)$

El tiempo de cada turno es constante.

Tiempo total

Resumiendo los apartados anteriores, obtenemos que el tiempo de ejecución del algoritmo es , o . $O(V^{3}+VE)$ ${\ estilo de visualización O (V ^ {3})}$

Notas

↑ Un nuevo enfoque al problema del flujo máximo. - 1986. - S. 136-146. — (Simposio anual de ACM sobre teoría de la computación, Actas del decimoctavo simposio anual de ACM sobre teoría de la computación). — ISBN 0-89791-193-8 .
↑ Para una prueba de que la última afirmación se deriva de la penúltima, véase el artículo " Red de transporte ".

Literatura

Thomas Kormen et al Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 2ª ed. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 . , capítulo 26