Vamos definir redes residuais e caminhos de aumento, particularmente dentro do contexto de algoritmos de fluxo de rede, como o método Ford-Fulkerson.

1. Rede residual:

Imagine que você tem uma rede com uma (s) fonte (s), um pia (t) e bordas com capacidades representando o fluxo máximo permitido através de cada borda. A * Rede Residual * é uma representação da capacidade restante na rede * depois que uma certa quantidade de fluxo já foi pressionada por ela.

Aqui está como funciona:

* bordas para a frente: Para cada borda (u, v) na rede original com capacidade c (u, v) e fluxo de corrente F (u, v), a rede residual inclui uma borda * para frente * (u, v) com capacidade c
* bordas para trás: A parte crucial é que a rede residual *também *inclui *bordas para trás *. Para cada borda (u, v) na rede original com fluxo atual f (u, v), a rede residual contém uma borda para trás (v, u) com capacidade C _f (v, u) =f (u, v). Isso representa a possibilidade de empurrar o fluxo de volta * ao longo da borda, cancelando efetivamente parte do fluxo já enviado. A capacidade da borda para trás é igual ao fluxo atualmente na borda para a frente, porque você só pode pressionar a quantidade de fluxo que já está lá.

Em essência, a rede residual mostra a capacidade disponível de alterações no fluxo. Ele se adapta dinamicamente à medida que o fluxo é empurrado pela rede. Encontrar um caminho de aumento (explicado abaixo) na rede residual significa que ainda há potencial para aumentar o fluxo total da fonte para a pia.


2. Caminho de aumento:

Um caminho de aumento * é um caminho simples (sem vértices repetidos) na rede residual que leva da (s) fonte (s) ao (s) pia (t). Fundamentalmente, representa uma maneira de aumentar o fluxo total através da rede.

A quantidade pela qual o fluxo pode ser aumentado ao longo do caminho de aumento é determinado pela capacidade *de gargalo *. Essa é a capacidade residual mínima entre todas as bordas no caminho de aumento.

Por exemplo:

Se um caminho de aumento tiver arestas com capacidades residuais de 5, 3 e 7, a capacidade de gargalo é 3. Podemos aumentar o fluxo ao longo desse caminho em 3 unidades. Esse processo atualiza o fluxo na rede original e subsequentemente modifica a rede residual.

Relação entre redes residuais e caminhos de aumento:

O núcleo de muitos algoritmos Max-Flow (como Ford-Fulkerson) é iterativamente:

1. Encontre um caminho de aumento na rede residual atual.
2. Aumentar o fluxo Ao longo desse caminho pela capacidade de gargalo.
3. Atualize a rede residual Para refletir a mudança no fluxo.

Esse processo continua até que não possam ser encontrados mais caminhos de aumento na rede residual; momento em que o fluxo máximo foi alcançado. O teorema do Min-Cut Min-Flow garante isso.