Gráfico residual no fluxo máximo

14

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?

csds
fonte

Respostas:

28

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 fe/ce denota tanto o fluxo fe empurrado através de uma aresta e quanto a capacidade ce dessa aresta):

Exemplo em execução

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 ePst ); isto é, todas as arestas em P têm capacidade disponível.e(ePfe<ceP
  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 ) .ΔΔPΔ=mineP(cefe)
  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 3GP1P2P3

Possível execução da abordagem gananciosa para fluxo máximo

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 2P3P1P2

Caminho de bloqueio

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:vwv

Fluxo inverso

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 ) GRGGe=(u,v)G

  • Uma aresta dianteira com capacidade , se .c e - f e c e - f e > 0e=(u,v)cefecefe>0

  • Uma aresta traseira com capacidade , se .f e f e > 0e=(v,u)fefe>0 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 3RP3

Gráfico residual

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 RwvstR

Caminho de aumento no gráfico residual

Em geral:

Quando um caminho de aumento é selecionado no gráfico residual :PR

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

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.GfGst

Mario Cervera
fonte
Existe um exemplo em que os caminhos são adicionados na ordem do menor comprimento, conforme descrito no algoritmo de Edmonds-Karp? No seu exemplo de contador, o primeiro caminho é o comprimento 3, enquanto um caminho mais curto (ou seja, 2) pode ser encontrado e seria adicionado primeiro se estivermos fazendo Edmonds-Karp.
24518 Roy Roy
Você pode simplesmente fazer com que todos os caminhos no gráfico original tenham tamanho 3 . Para fazer isso, divida o vértice v em dois vértices v 1 e v 2 . Em seguida, divida w em w 1 e w 2 . Adicione também duas arestas ( v 1 , v 2 ) e ( w 1 , w 2 ) com capacidade 2 . A borda que originalmente foi de v para w agora passa dest3vv1v2ww1w2(v1,v2)(w1,w2)2vw a w 2 . Podemos obter o mesmo tipo de fluxo de bloqueio se escolhermos inicialmente o caminho que contém a aresta ( v 1 , w 2 ) . v1w2(v1,w2)
Mario Cervera
Seu exemplo faz sentido. Sempre podemos estender o gráfico em outras arestas do corte para fazer com que a aresta em questão esteja em um dos caminhos mais curtos.
Roy Roy
3

ABBAAB

Banach Tarski
fonte