algorithm - método - flujo maximo ford fulkerson ejercicios resueltos

¿Qué es exactamente el camino de aumento?

Question

Cuando se habla sobre la computing network flows , el Manual de Diseño de Algoritmos dice:

Los algoritmos de flujo de red tradicionales se basan en la idea de aumentar las rutas y encontrar repetidamente una ruta de capacidad positiva de s a t y agregarla al flujo. Se puede demostrar que el flujo a través de una red es óptimo si y solo si no contiene una ruta de aumento.

No entiendo qué es el augmenting paths . Busqué en Google y encontré:

• Aumento del camino en Wolfram

• Red de flujo en Wiki

pero todos hacen referencia a la cita anterior.

¿Alguien puede por favor explicar claramente qué es un augmenting path ?

Answer 1

¿Y cómo averiguas el camino de aumento de la fuente al sumidero? Usando la versión modificada de BFS. Realiza BFS desde el origen hasta que llega al sumidero y atraviesa un borde solo si tiene capacidad residual (es decir, para ese borde, su capacidad máxima - flujo de corriente> 0). Y para este camino desde el origen al sumidero, mantienes la capacidad residual mínima, que es el flujo máximo que puedes atravesar por ese camino. Fragmento de código de alto nivel para obtener la idea:

bool maxFlowAchieved = false;
int maxFlow = 0;  // keeps track of what is the max flow in the network
while(!maxFlowAchieved)
{
    //BFS returns collection of Edges in the traversal order from source to sink
    std::vector<Edge*> path = BFS(source, sink); 
    maxFlowAchieved = path.size() == 0;  // all paths exhausted
    if(maxFlowAchieved)
        break;
    // traverse each edge in the path and find minimum residual capacity
    // edge->residual = edge->maxCapacity - edge->currentflow
    int allowedFlow = GetMinResidualOnPath(path);
    // Now add additional flow to each edge in the path. 
    // i.e. for each edge in path, edge->currentflow += allowedFlow
    // clearly, edge->currentflow + allowedFlow <= edge->maxCapacity
    SaturatePath(path, allowedFlow);
    maxFlow += allowedFlow;
}

return maxFlow;

Answer 2

Aumentar significa aumentar, hacer más grande. En una red de flujo dada G=(V,E) y un flujo f un camino de aumento p es una ruta simple desde la source s al sink t en la red residual Gf . Mediante la definición de residual network , podemos aumentar el flujo en un borde (u,v) de un camino de aumento hasta una capacidad Cf(u,v) sin violar la restricción, en cualquiera de (u,v) y (v,u) está en la red de flujo original G También la cantidad máxima por la cual podemos aumentar el flujo en cada borde en una ruta aumentada p se denomina residual capacity of p . La demostración se puede encontrar en la introducción a los algoritmos por thomas h. cormen etc ...

Answer 3

Un proceso de búsqueda de flujos desde la fuente hasta el sumidero de forma iterativa. Por ejemplo, en el caso del algoritmo de Ford-Fulkerson, inicialmente todos los flujos en todos los bordes son cero. En la iteración tomamos los valores para cada ruta / borde que nos lleva a encontrar flujos llamados caminos de aumento.

Answer 4

Una ruta de aumento es una ruta simple, una ruta que no contiene ciclos, a través del gráfico que usa solo bordes con capacidad positiva desde la fuente hasta el receptor.

Por lo tanto, la afirmación anterior es de alguna manera obvia: si no puede encontrar una ruta desde el origen hasta el sumidero que solo usa bordes de capacidad positiva, entonces no se puede aumentar el flujo.

Por cierto, la prueba de esa afirmación no es tan fácil.