Data de Aula: 06-Jun-2003
Redator: Carlos R. Senna - RA
022.248
Nessa ata vamos examinar um grafo orientado e interpretá-lo como uma Rede de Fluxo usando-o para analisar fluxo de materiais a partir de uma origem, onde o material é produzido, até um depósito, onde o material é consumido. A origem produz o material a uma taxa fixa, e o depósito consome o material na mesma taxa. O "fluxo" do material em qualquer ponto no sistema é intuitivamente a taxa na qual o material se move.
Cada aresta orientada pode ser imaginada como um canal, com uma capacidade estabelecida, dada como uma taxa máxima na qual o material pode fluir pelo canal. Vértices são junções de canais, onde o material flui sem acumulação. Isto é, com exceção da origem e do destino, a taxa de entrada e de saída de material no vértice deve ser a mesma. Chamamos essa propriedade de "conservação do fluxo".
Com essas premissas vamos estudar o problema de fluxo máximo, onde desejamos calcular a maior taxa na qual o material pode ser enviado da origem até o depósito.
É importante observar que nessa ata usaremos uma terminologia diferente da adotada pelo livro texto no capítulo 26. Usaremos "Redes de Fluxo" e não "Fluxo em Redes" para o termo "flow network". Usaremos "antisimetria" e não "simetria ablíqüa".
Uma rede de fluxo G = (V, E) é um grafo orientado completo em que cada aresta (u, v) ∈ E tem uma capacidade c(u, v) >= 0 (não negativa). Se uma dada aresta não está em E, então supomos que a sua capacidade é zero (no livro texto tais arestas não são desenhadas nos grafos). Numa rede de fluxo temos dois vértices especiais, origem s e um depósito t, e para todo vértice v do grafo existe um caminho a partir de s passando por v que chega em t.
Fig A-1
Na figura A-1 acima (livro texto pag. 511 Fig. 26.1 (a)), temos uma rede de fluxo para o problema de distribuição de produtos. A fábrica da empresa fica em Vancouver e seu depósito em Winnipeg. Os vértices intermediários indicam as cidades entre a fábrica e o depósito por onde os produtos podem ser transportados. Cada aresta é identificada pela sua capacidade c(u,v) (diária) de transporte.
Definimos um fluxo como um valor que atribuímos a cada aresta do grafo. De um modo mais formal, dizemos um fluxo em G = (V, E) como uma função de valor real f : V x V -> R, que satisfaz a três propriedades:
Restrição de capacidade: Para todos u, v ∈ V, exigimos f (u, v) <= c (u, v). Ou seja, um fluxo não pode exceder à capacidade da aresta.
Antisimetria: Para todos u, v ∈ V, exigimos f (u, v) = -f (v, u).
Conservação de fluxo: Para todo u ∈ V - {s,t}, exigimos
A quantidade f (u, v), é chamada de fluxo do vértice u até o vértice v.
Pela propriedade de conservação de fluxo, o fluxo total de um vértice é 0 (zero), sendo que esse vértice não pode ser a origem, nem o depósito. Prof. Meidanis observou que o somatório referente à conservação do fluxo é para cada vértice, e não para o grafo. Exemplificou essa propriedade usando a rede da fábrica apresentado acima (fig. A-1), dizendo que os caminhões que transportam os produtos passam pela cidades durante o caminho, mas em nenhuma delas eles podem armazenar os produtos. Somente a fábrica e o depósito tem essa capacidade. Prof. Meidanis e Patrick construíram a rede abaixo (fig. A-2) para ilustrar o assunto.
Fig. A-2
Os número em azul indicam os fluxos, e os valores em vermelho indicam as capacidades. Repare que em todos os vértices temos conservação de fluxo.
O valor de um fluxof é definido como:
ou seja, o fluxo total que sai da origem. No exemplo da fig. A-2 o valor é 3.
Um fluxo máximo é um fluxo de valor máximo. Uma distribuição é um caminho possível. Na fig A-2 temos uma distribuição que passa pelo vértice v1 e vai para o vértice v3, e temos outra que passa por v1 e vai para v2.
Na figura A-3 abaixo (livro texto pag. 511 Fig. 26.1 (b)), temos mais um exemplo com um fluxo f em G com valor | f | = 19. São mostrados apenas fluxos positivos. Se f (u, v) > 0, a aresta (u, v) é identificada por f (u, v)/ c(u, v). Se f (u, v) <= 0, a aresta (u, v) é identificada apenas por sua capacidade.
Fig. A-3
O método de Ford-Fulkerson tem por objetivo encontrar um fluxo máximo para uma rede de fluxos. É chamado de método por englobar diversas implementações com diferentes tempos de execução. O método é iterativo, começando com f (u, v) = 0 para todo u, v ∈ V dando um fluxo inicial o valor 0. A cada iteração aumentamos o valor do fluxo encontrando um caminho aumentante, que podemos imaginar como um caminho de s a t onde podemos empurra mais fluxo e depois aumentar o fluxo ao longo desse caminho. O processo é repetido até não sejam encontramos mais caminhos aumentantes.
MÉTODO FORD-FULKERSON(G, S, T) 1 iniciar fluxo f como 0 2 while existir um caminho aumentante p 3 do ampliar fluxo f ao longo de p 4 return f
Intuitivamente uma rede residual consiste em arestas que podem admitir mais fluxo. Na fig A-2 a aresta que liga v1 a v3 tem fluxo = 1 e capacidade = 6. Essa aresta tem capacidade residual de 5, e portanto estaria na rede residual desse grafo. De um modo mais formal, considere que temos uma rede de fluxo G = (V, E), com origem s e depósito t. Seja f um fluxo em G, e considere um par de vértices u, v ∈ V. A quantidade de fluxo adicional que podemos empurrar desde u até v e que não ultrapasse a capacidade c(u, v) é a capacidade residual de (u, v) dada por:
cf (u, v) = c(u, v) - f (u, v)
Quando o fluxo f (u, v) é negativo, a capacidade residual cf (u, v) é maior que a capacidade c(u, v).
Dados uma rede de fluxo G = (V, E) e um fluxo f , a rede residual de G induzida por f é Gf = (V, ), onde
Ef = {(u, v) ∈ V x V : cf (u, v) > 0}.
A figura A-4 abaixo(livro texto pag. 516 Fig. 26.3 (b)), mostra a rede residual gerada a partir da fig. A-3.
Fig. A-4
Dados uma rede de fluxo G = (V, E) e um fluxo f , um caminho aumentante p é um caminho simples desde s até t na rede residual Gf constituído por arestas estritamente positivas. Se o fluxo na rede não é máximo, sempre existe um caminho aumentante. O caminho demarcado na fig. A-4 acima é um caminho aumentante.
De maneira geral um corte de uma rede de fluxo é dividir o grafo em duas partições onde os vértices de origem e destinos fiquem separados. Podemos definir um corte(S, T) de uma rede de fluxo G = (V, E) é uma partição de V em S e T = V - S tal que s ∈ S e t ∈ T. Se f é um fluxo, então o fluxo líquido pelo corte(S, T) é definido como f (S, T). A capacidade do corte(S, T) é c(S, T) dada pela soma das capacidades das arestas que cruzam o corte feito com origem em S e chegam em T. Um corte mínimo de uma rede é um corte cuja capacidade é mínima dentre todos os cortes da rede.
A figura A-5 abaixo (livro texto pag. 519 Fig. 26.4), mostra um corte(S, T), onde S = {s, v1, v2 } e T = {v3, v4, t}. Os vértices em S são pretos, e os em T são brancos. O fluxo líqüido por (S, T) é f (S, T) = 19, e a capacidade é c(S, T) = 26.
(livro texto) Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática, 2002.