MO405 - Atas das Aulas

4.3 Network Flow Probrems (problemas de fluxo de rede)

Objetivo do capítulo: modelar o fluxo de redes (mandar um fluxo da origem ao destino) e trabalhar com problemas de otimização.

O grafo utilizado para os problemas de fluxo de rede é um grafo orientado tendo um vértice s como fonte e um vértice t como sorvedouro; a cada aresta e está associado um valor não negativo que representa sua capacidade c(e).

O fluxo f(e) é uma função que associa a cada aresta um valor real, que corresponde ao fluxo que está passando por aquela aresta.

Restrições ao fluxo:
    - restrição de capacidade: 0 <= f(e) <= c(e)
    - restrição de conservação: f+(v) = f-(v), para todo vértice do grafo exceto s e t (fonte e sorvedouro)
        onde     f+(v) é o fluxo que sai de v
                    f-(v) é o fluxo que entra em v

Um fluxo é factível quando obedece às duas restrições ao fluxo.

Fluxo máximo é o fluxo factível cuja diferença f-(t) - f+(t) é máxima (quantidade de fluxo que "se acumula" no sorvedouro é máxima).
O fluxo máximo pode ser medido em s como o máximo da diferença: f+(s) - f-(s)

Dado um fluxo em uma rede N, um caminho f-aumentante é um caminho P da fonte ao sorvedouro no grafo subjacente G, tal que para cada aresta e de E(P) temos:
- se e em P segue na direção do sorvedouro, então f(e) < c(e)
- se e em P segue na direção contrária ao sorvedouro, então f(e) > 0.

Associada a esta definição está a definição de tolerância que é o o mínimo valor da diferença: c(e) - f(e) quando e está na direção do sorvedouro e f(e) quando está na direção contrária ao sorvedouro.

Dado um caminho f-aumentante, a tolerância deste é o valor o qual o fluxo pode ser aumentado ao longo deste caminho.

O valor do fluxo máximo factível é igual a menor capacidade um corte (por arestas) fonte-sorvedouro.

Abaixo um exemplo de fluxo em rede. Entre parênteses temos o valor do fluxo; fora dos parênteses temos a capacidade. Na primeira figura o fluxo não é máximo. Existe um caminho aumentante. Na segunda figura, o fluco foi aumentado em uma unidade, usando-se o caminho aumentante em questão.

Algoritmo de rotulação: acha caminho aumentante ou exibe um corte mínimo: trabalha com vértices alcançados e explorados. No início, apenas a fonte está como alcançada. A cada passo, um vértice alcançado mas não explorado é explorado.
Acaba quando alcança o sorvedouro ou quando não houver mais quem explorar.
Complexidade (do algoritmo de rotulação): ordem de (n + m).
Se os vértices forem explorados em largura, então não há mais do que ordem de n^3 rotulações.

Fluxos inteiros: se todas as capacidades da rede são valores inteiros então existe um fluxo máximo com valor de fluxo (em cada aresta) inteiro.