Gráfico residual no fluxo máximo

Estou lendo sobre o problema do fluxo máximo aqui . Eu não conseguia entender a intuição por trás do gráfico residual. Por que estamos considerando as arestas traseiras ao calcular o fluxo?

Alguém pode me ajudar a entender o conceito de gráfico residual?

Como o algoritmo muda nos gráficos não direcionados?

A intuição subjacente ao gráfico residual no problema de vazão máxima é muito bem apresentada nesta palestra. A explicação é a seguinte.

Suponha que estamos tentando resolver o problema de fluxo máximo para a seguinte rede $G$ (onde cada etiqueta $f_e/c_e$ denota tanto o fluxo $f_e$ empurrado através de uma aresta $e$ quanto a capacidade $c_e$ dessa aresta):

Uma possível abordagem gananciosa é a seguinte:

1. Escolha um caminho de aumento arbitrário que vai do vértice de origem s ao vértice coletor t de modo que ∀ $P$$s$$t$ ); isto é, todas as arestas em P têm capacidade disponível.$\forall e \: (e \in P \rightarrow f_e \lt c_e$$P$
2. Empurre o fluxo máximo possível por esse caminho. O valor de Δ é determinado pelo gargalo de P ; isto é, a borda com capacidade disponível mínima. Formalmente, Δ = min e ∈ P ( c e - f e ) .$\Delta$$\Delta$$P$$\Delta=\min_{e \in P} (c_e-f_e)$
3. Vá para a etapa 1 até que não haja caminhos de aumento.

Ou seja, encontre um caminho com capacidade disponível, envie fluxo ao longo desse caminho e repita.

Em , uma possível execução da heurística acima encontra três caminhos de aumento , e , nesta ordem. Esses caminhos empurram 2, 2 e 1 unidades de fluxo, respectivamente, para um fluxo total de 5:P 1 P 2 P $G$$P_1$$P_2$$P_3$

Escolher caminhos nesta ordem leva a uma solução ideal; no entanto, o que acontece se selecionarmos primeiro (ou seja, antes de e )?P 1 P $P_3$$P_1$$P_2$

Temos o que chamamos de fluxo de bloqueio : não existem mais caminhos de aumento. Nesse caso, o fluxo total é 3, o que não é ideal. Esse problema pode ser resolvido permitindo operações de desfazer (ou seja, permitindo que o fluxo seja enviado ao contrário, desfazendo o trabalho de iterações anteriores): basta empurrar 2 unidades de fluxo para trás do vértice para o vértice seguinte maneira:$w$$v$

Codificar essas operações de desfazer permitidas é o principal objetivo do gráfico residual .

Um gráfico residual de uma rede tem o mesmo conjunto de vértices que e inclui, para cada aresta :G G e = ( u , v ) ∈ $R$$G$$G$$e=(u,v) \in G$

• Uma aresta dianteira com capacidade , se .c e - f e c e - f e > $e'=(u,v)$$c_e-f_e$$c_e-f_e \gt 0$

• Uma aresta traseira com capacidade , se .f e f e > $e''=(v,u)$$f_e$$f_e \gt 0$

Por exemplo, considere o gráfico residual que é obtido após a primeira iteração da heurística gananciosa quando a heurística seleciona primeiro (ou seja, quando obtém o fluxo de bloqueio):P $R$$P_3$

Observe que a operação desfazer que empurra 2 unidades de fluxo de para é codificada como um caminho de avanço (aumento) de para em :v s t $w$$v$$s$$t$$R$

Em geral:

Quando um caminho de aumento é selecionado no gráfico residual :$P'$$R$

• Cada aresta em que corresponde a uma aresta dianteira em aumenta o fluxo usando uma aresta com capacidade disponível.$P'$$G$
• Toda aresta em que corresponde a uma aresta retrocedendo em desfaz o fluxo que foi empurrado na direção anterior no passado.$P'$$G$

Essa é a principal idéia por trás do método Ford – Fulkerson .

O método Ford-Fulkerson segue exatamente da mesma maneira que a abordagem gananciosa descrita acima, mas só para quando não há mais caminhos de aumento no gráfico residual (não na rede original). O método está correto (ou seja, sempre calcula um fluxo máximo) porque o gráfico residual estabelece a seguinte condição de otimização :

Dada uma rede , um fluxo é máximo em , se não houver caminho no grafo residual.$G$$f$$G$$s-t$

$A$$B$$B$$A$$A$$B$