Rede de fluxo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em teoria dos grafos, um rede de fluxo (também conhecida como uma rede de transporte) é um grafo orientado, onde cada aresta tem uma capacidade e cada aresta recebe um fluxo. A quantidade de fluxo em uma borda não pode exceder a capacidade da borda. Muitas vezes em Pesquisa Operacional, um grafo orientado é chamado de uma rede, os vértices são chamados de nós e as arestas são chamados de arcos. Um fluxo deve satisfazer a restrição de que a quantidade de fluxo em um nó é igual a quantidade de fluxo de fora, a menos que seja uma fonte, que tem apenas de fluxo de saída, que não tem fluxo de entrada. Uma rede pode ser utilizado para modelar o tráfego no sistema viário, a circulação das demandas, fluidos em tubos, correntes em um circuito elétrico, ou qualquer coisa semelhante alguma coisa que viaja através de uma rede de nós.

Definição[editar | editar código-fonte]

Uma rede é um grafo G = (V, E), juntamente com uma  função não-negativa c: V × V → ℝ, chamado de capacidade de função. Sem perda de generalidade, assume-se que se (u, v) ∈ E , em seguida, (v, u) é também um membro de E, uma vez que se (v, u) ∉ E , em seguida, (v, u) pode ser adicionado a E e, em seguida, a definição de c(v, u) = 0.

Se dois nós em G são distintos, uma fonte s e um dissipador de t, então (G, c, s, t) é chamado rede de fluxo.[1]

Fluxos[editar | editar código-fonte]

Há várias noções de um fluxo de função, que pode ser definido em um grafo de fluxo. O fluxo de funções do modelo, o fluxo líquido de unidades entre pares de nós, e são úteis quando fazemos perguntas como qual é o número máximo de unidades que podem ser transferidos a partir do nó de origem s para o nó saída t? O exemplo mais simples de um fluxo de função é conhecida como um pseudo-fluxo.

Um pseudo-fluxo é uma função f : V × V → ℝ que satisfaz os dois seguintes restrições para todos os nós u e v:
  • Inclinação simetria: Apenas codificar o fluxo líquido de unidades entre um par de nós u e v (ver intuição abaixo), que é: f (u, v) = −f (v, u).
  • Restrição de capacidade: Um arco de fluxo não pode exceder a sua capacidade, isto é: f (u, v) ≤ c(u, v).

Dado um pseudo-fluxo de f em um rede de fluxo, muitas vezes, é útil considerar o fluxo líquido entrar em um determinado nó v, isto é, a soma dos fluxos que entram v. O excesso de função xf : V → ℝ é definida por xf (u) = ∑vV f (v, u). Um nó u é dito ser ativo se xf (u) > 0, deficiente se xf (u) < 0 ou conservação , se xf (u) = 0.

Estas final definições de levar a dois fortalecimentos a definição de um pseudo-fluxo:

Um pré-fluxo é um pseudo-fluxo que, para todo vV \{s}, satisfaz a restrição adicional:
  • Não-deficiente fluxos: O fluxo líquido de inserir o nó v é não-negativo, exceto para a fonte, que "produz" o fluxo. O que é: xf (v) ≥ 0 para todo vV \{s}.
Um viável fluxo, ou apenas um fluxo, é um pseudo-fluxo que, para todo vV \{s, t}, satisfaz a restrição adicional:
  • O fluxo de conservação: O fluxo líquido de inserir o nó v é 0, exceto para a fonte, que "produz" o fluxo, e a pia, que "consome" de fluxo. O que é: xf (v) = 0 para todo vV \{s, t}.

O valor de um possível fluxo de f, denotada | f |, é o fluxo líquido na pia t do rede de fluxo. Isto é, | f | = xf (t).

Intuição[editar | editar código-fonte]

No contexto de análise de fluxo, há apenas um interesse em como as unidades são transferidos entre nós em uma visão holística. Dito de outra forma, não é necessário distinguir vários arcos entre um par de nós:

  • Diante de quaisquer dois nós u e v, se existem dois arcos a partir de u para v , com capacidades de 5 e 3 , respectivamente, isto é equivalente a considerar somente um único arco entre u e v com capacidade de 8 — é útil apenas para saber que 8 unidades podem ser transferidos a partir de u para v, e não como eles podem ser transferidos.
  • Novamente, dado dois nós u e v, se há um fluxo de 5 unidades a partir de u para v, e um outro fluxo de 3 unidades de v para u, isto é equivalente a um fluxo líquido de 2 unidades a partir de u para v, ou um fluxo líquido de −2 unidades de v para u (para o sinal indica o sentido) — ela é útil apenas para saber que um fluxo líquido de 2 unidades de fluxo entre u e v, e a direção que eles vão fluir, não como que o fluxo líquido é alcançado.

Por esta razão, a capacidade de função c: V × V → ℝ, o que não permite que vários arcos inicial e final ao mesmo nós, é suficiente para a análise de fluxo. Da mesma forma, é suficiente para impor a inclinação simetria restrição no fluxo de funções para garantir que o fluxo entre dois vértices é codificado por um único número (para indicar a magnitude), e um sinal (para indicar a direção) — conhecendo o fluxo entre u e v implicitamente, através da distorção da simetria, sabe o fluxo entre v e u. Estas simplificações do modelo não são sempre imediatamente intuitivo, mas eles são convenientes quando chega o momento de analisar os fluxos.

A restrição de capacidade , simplesmente, garante que o fluxo em qualquer um arco dentro da rede não pode exceder a capacidade do arco.

Conceitos úteis para problemas de fluxo[editar | editar código-fonte]

Resíduos[editar | editar código-fonte]

A capacidade residual de um arco com respeito a um pseudo-fluxo de f, denotado cf, é a diferença entre o arco da capacidade e seu fluxo. Isto é, cf (e) = c(e) - f(e). A partir disso, podemos construir um residual de rede, denotado Gf (V, Ef), que modela o montante disponível a capacidade do conjunto de arcos de G = (V, E). Mais formalmente, dado um rede de fluxo GG, a rede residual Gf tem o conjunto de nós V, arco Ef = {eE : cf (e) > 0} e a capacidade de função cf.

Este conceito é usado de Ford–Fulkerson algoritmo que calcula a vazão máxima em um rede de fluxo.

Observe que pode haver um caminho de u para v em o residual de rede, mesmo que não existe um caminho de u para v na rede original. Desde que flui em direções opostas cancelar, diminuindo o fluxo de v para u é o mesmo que aumentar o fluxo de u para v.

Caminho ampliado[editar | editar código-fonte]

Um caminho ampliado é um caminho (u1, u2, ..., uk) na rede residual, onde u1 = s, uk = t, e cf (ui, ui + 1) > 0. Uma rede esta em fluxo máximo se e somente se não há aumentando caminho na rede residual Gf.

Várias fontes e/ou dissipadores [editar | editar código-fonte]

Às vezes, as necessidades de um modelo de uma rede com mais de uma fonte, um super recurso é introduzido para o gráfico.[2] Este consiste de um vértice ligado a cada uma das fontes, com bordas de capacidade infinita, assim como para atuar como uma fonte global. Semelhante construção de poços é chamado de um super poços.[3]

Exemplo[editar | editar código-fonte]

Uma rede de fluxo, mostrando o fluxo e  capacidade 

Para a esquerda, você verá um rede de fluxo com origem rotulado s, poço t, e de mais quatro nós. O fluxo e a capacidade é denotado . Observe como a rede defende a distorção da simetria, as restrições de capacidade e fluxo de conservação. A quantidade total de fluxo a partir de s a t é 5, o que pode ser facilmente visto a partir do fato de que o total de saída de fluxo a partir de s é 5, que é também a entrada de fluxo para t. Sabemos que não há fluxo aparece ou desaparece em qualquer um dos outros nós.

Residual de rede de fluxo acima de rede, mostrando capacidade residual.

Abaixo você vê o residual de rede para um determinado fluxo. Observe como há positivos da capacidade residual em algumas bordas, onde a capacidade original é zero, por exemplo, para a borda . Este fluxo não é um fluxo máximo. Não há capacidade disponível ao longo dos caminhos , e , que são, em seguida, a aumentar caminhos. A capacidade residual do primeiro caminho é

.[citação necessários] Observe que enquanto existir algum caminho com uma positiva da capacidade residual, o fluxo não vai ser o máximo. A capacidade residual para algum caminho é o mínimo da capacidade residual de todas as arestas do caminho.
Algoritmos conhecidos para Max-Flow
Inventor(s) Ano Tempo

complexidade

Edmonds–Karp algoritmo 1972 O(m2n)
MPM (Malhotra, Pramodh-Kumar e Maheshwari)

o algoritmo de[4]

1978 O(n3)
J. Orlin 2013 O(mn)

Aplicações[editar | editar código-fonte]

Imagem de uma série de tubos de água, a montagem em uma rede. Cada tubo é de um determinado diâmetro, então ele só pode manter um fluxo de uma certa quantidade de água. Em qualquer lugar que os tubos se encontram, a quantidade total de água em que a junção deve ser igual à quantidade de sair, caso contrário, seria rapidamente correr para fora da água, ou teríamos um acúmulo de água. Temos uma entrada de água, que é a fonte, e uma saída, a pia. Um fluxo, então, seria um caminho possível para a água da fonte para o coletor de modo que a quantidade total de água que sai da tomada é consistente. Intuitivamente, o fluxo total de uma rede é a taxa na qual a água sai da tomada.

Os fluxos podem dizer respeito a pessoas ou material sobre redes de transporte, ou a eletricidade ao longo de distribuição elétrica de sistemas. Para qualquer tipo de rede física, o fluxo de entrada em qualquer nó intermediário necessidades igual ao fluxo de saída do nó. Este conservação restrição é equivalente a lei actual de Kirchhoff.

Redes de fluxos também encontram aplicações em ecologia: redes de fluxo surgiu naturalmente quando se considera o fluxo de nutrientes e energia entre diferentes organizações de uma cadeia alimentar. Os problemas matemáticos, associados com tais redes são bastante diferentes daquelas que surgem em redes de líquido ou fluxo de tráfego. O campo de ecossistema de análise de rede, desenvolvido por Robert Ulanowicz e outros, envolve a utilização de conceitos da teoria da informação e da termodinâmica para estudar a evolução destas redes ao longo do tempo.

O mais simples e mais comum de problema usando redes de fluxos é encontrar o que é chamado de fluxo máximo, o que proporciona maior fluxo total da fonte para o receptor em um gráfico dado. Existem muitos outros problemas que podem ser resolvidos usando o max fluxo de algoritmos, se forem adequadamente modelado como redes de fluxos, tais como bipartido correspondência, a atribuição de problema e o problema do transporte. Vazão máxima problemas podem ser resolvidos de forma eficiente com o relabel-to-front algoritmo. O max-flow min-cut teorema afirma que a busca de uma prova de rede de fluxo é equivalente a encontrar um corte de capacidade mínima que separa a fonte e o receptor. Que um corte é a divisão de vértices tal que a origem está em uma divisão e a pia é em outro.

Em umamulti-commodity fluxo de problema, você tem várias fontes e sumidouros, e vários "commodities", que são a fluir a partir de uma determinada origem para um determinado receptor. Este poderia ser, por exemplo, vários bens que são produzidos em fábricas diferentes, e devem ser entregues para várias dado clientes através da mesma rede de transporte.

Em um problema de fluxo de custo mínimo, a cada aresta tem um determinado custo e o custo de envio do fluxo de em toda a borda é . O objetivo é enviar uma determinada quantidade de fluxo da fonte para o receptor, ao menor preço possível.

Em umaproblema de circulação, você tem um limite inferior nas bordas, além de o limite superior . Cada borda também tem um custo. Muitas vezes, o fluxo de conservação vale para todos nós um problema da circulação, e existe uma ligação entre o receptor para a fonte. Desta forma, você pode ditar o fluxo total com e . O fluxo que circula através da rede, daí o nome do problema.

Em uma rede com ganhos ou generalizada rede cada aresta tem um ganho, um número real (não zero) tal que, se o edge tem ganho g, e uma quantidade x flui para a borda em sua extremidade e, em seguida, uma quantidade gx flui na cabeça.

Em uma fonte de problema de localização, um algoritmo tenta identificar a fonte mais provável de nó de difusão de informações através de um parcialmente observado na rede. Isso pode ser feito em tempo linear e árvores cúbicos de tempo arbitrários redes e tem aplicações que vão desde o acompanhamento de usuários de telefone celular para identificar a origem da aldeia de surtos de doenças.[5]

Ler mais[editar | editar código-fonte]

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. A.V. Goldberg, É.
  2. Black, Paul E. "Supersource".
  3. Black, Paul E. "Supersink".
  4. Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). «An algorithm for finding maximum flows in networks». Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9 
  5. http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf

Outras leituras[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]