Please enable JavaScript.
Coggle requires JavaScript to display documents.
FLUXO EM GRAFOS (Exemplos de aplicações (Envio de produtos do produtor ao…
FLUXO EM GRAFOS
Exemplos de aplicações
-
-
-
líquido fluindo por uma rede de tubos, como a rede de abastecimento de água ou a rede de esgoto ou gás
-
Voz, imagem ou dados em redes de comunicação
-
-
-
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)
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.
CAMINHOS AUMENTANTES
-
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.
-
Propriedades do Fluxo
-
-
O fluxo que entra deve ser igual ao que sai, exceto na origem e no sumidouro.
MÉTODO DE FORD-FULKERSON
3 ideias importantes
-
-
Cortes: Separam o grafo em duas partes, uma como o nó de origem e outra com o sumidouro
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.
