FLUXO EM GRAFOS
FLUXO EM REDES
É a transferência de algum tipo de recurso quantificável e sujeito a restrições de equilíbrio, de um local (nó origem/raiz) para outro (nó sumidouro) através da rede.
O Fluxo é o envio de entidades de um nó (origem) até outro nó (destino), percorrendo alguns dos arcos da rede onde aqueles nós fazem parte.
Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta (u,v) pertence a E e tem uma capacidade não negativa.; onde E=conjunto de arestas, V=conjunto de vértices, u = origem, v= sumidouro(destino)
Propriedades do Fluxo
O fluxo que circulará em um grafo deve ser igual ou menor que a capacidade máxima deste fluxo.
fluxo em uma direção deve ser igual ao seu fluxo na direção oposta.
O fluxo que entra deve ser igual ao que sai, exceto na origem e no sumidouro.
Rede de Fluxos com múltiplas fontes e/ou destinos:
A empresa poderia ter mais que uma fábrica e mais que um depósito;
não está de acordo com a definição de rede uma única fonte e um único destino;
Transformamos em uma rede equivalente
Definir super-fonte que liga a todas as fontes
Definir super-destino ao qual todos os destinos se ligam.
Capacidades infinitas entre super-fonte e fontes, e entre destinos e super destino.
Fluxo máximo
Número máximo de unidades de fluxo que é possível enviar através da rede desde o nó origem até o nó destino sem violar quaisquer restrições de capacidade.
Considera-se que há conservação de fluxo, ou seja, que o fluxo parte da origem e chega totalmente ao destino, não havendo perdas no caminho.
Exemplos de aplicações
Envio de produtos do produtor ao distribuidor.
O deslocamento das pessoas das suas casas para os locais de trabalho
A expedição de cartas desde a estação de correio até os seus destinatários.
líquido fluindo por uma rede de tubos, como a rede de abastecimento de água ou a rede de esgoto ou gás
Peças se deslocando por linhas de montagem
Voz, imagem ou dados em redes de comunicação
sistemas elétricos de transmissão
MÉTODO DE FORD-FULKERSON
3 ideias importantes
Redes residuais: Consiste em arestas que podem admitir mais fluxo
Caminhos em ampliação: Consiste de um caminho simples desde a origem até a rede residual.
Cortes: Separam o grafo em duas partes, uma como o nó de origem e outra com o sumidouro
CAMINHOS AUMENTANTES
São caminhos simples da origem(s) ao sumidouro(t) destino através da rede residual Gf.
A capacidade residual de um caminho aumentante p, corresponde à menor dentre as capacidades residuais das arestas que fazem parte de p. Ou seja, refere-se à quantidade máxima pela qual o fluxo pode ser aumentado em um caminho.
ALGORITMO DE FORD-FULKERSON
1 - Escolhe-se um caminho qualquer desde a origem até o sumidouro cujas arestas tenham capacidade positiva (>0).
2 - Procurar nesse caminho o arco orientado com menor capacidade c
3 - Diminuir de c a capacidade de fluxo em cada aresta do caminho no sentido direto e aumentar de c a capacidade das arestas no sentido inverso.
Regressar ao 1º passo. Se já não existir nenhum caminho em que todas as arestas tenham capacidade positiva, então o fluxo máximo já está determinado.
CORTES DE FLUXO
Um corte de um fluxo é uma separação do conjunto de vértices em dois conjuntos.
Um corte mínimo de uma em rede é um corte cuja capacidade é mínima dentre todos os cortes da rede
TEOREMA DO FLUXO MÁXIMO: Para toda a rede com uma só origem e um só destino o fluxo máximo é igual ao valor mínimo de corte entre todos os cortes possíveis da rede.