Rede de fluxo

Em teoria dos grafos, uma rede de fluxo (também conhecida como rede de transporte) é um grafo orientado, onde cada aresta tem uma capacidade e recebe um fluxo. A quantidade de fluxo em cada aresta não pode exceder a capacidade associada à mesma. É comum, em ciência de redes e na investigação operacional, chamar aos grafos redes, aos vértices nós ou nodos, e às arestas arcos ou ligações. O fluxo total que chega a um nó deve ser igual ao fluxo total que sai do mesmo, exceto nos casos em que o nó é uma fonte, tendo apenas saída de fluxo, ou um sumidouro, caso em que tem apenas entrada de fluxo. As redes de fluxo podem ser usadas para modelar redes de transporte, como por exemplo: o tráfego no sistema viário, a circulação de bens, fluídos em tubos, ou correntes em circuitos elétricos.

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

Uma rede é um grafo $G = (V, E)$ , onde $V$ é um conjunto de vértices ou nós/nodos e $E$ um conjunto de arestas (em inglês edges), juntamente com uma função não-negativa $c : V \times V \to ℝ \infty$ , chamada capacidade. Sem perda de generalidade, podemos assumir que, se o par $(u, v) \in E$ , então $(v, u)$ é também um elemento de $E$ , uma vez que, se o elemento $(v, u) \notin E$ , este pode ser acrescentado a $E$ com capacidade $c (v, u) = 0$ .

Se dois nós em G são distintos, uma fonte $s$ e um sumidouro de $t$ , então $(G, c, s, t)$ é chamada 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 \times V \to ℝ

que satisfaz as duas restrições seguintes para todos os nós u e v:

Antissimetria: Apenas considerar o fluxo total de unidades entre um par de nós u e v (ver intuição abaixo), isto é: $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) \leq c (u, v)$ .

Dado um pseudo-fluxo de f numa 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 $x f : V \to ℝ$ é definida por $x f (u) = \sum v \in V f (v, u)$ . Um nó u é dito ser ativo se $x f (u) > 0$ , deficiente se $x f (u) < 0$ ou conservação , se $x f (u) = 0$ .

Estas definições finais conduzem a dois fortalecimentos da definição de pseudo-fluxo:

Um pré-fluxo é um pseudo-fluxo que, para todo

v ∈ V \{s

}, satisfaz a restrição adicional:

Não há fluxos não-deficientes: O fluxo total que entra num dado nó $v$ é não-negativo, exceto se este for a for fonte, que produz o fluxo. Isto é: $x f (v) \geq 0$ para todo $v ∈ V \{s$ }.

Um fluxo viável, ou apenas um fluxo, é um pseudo-fluxo que, para todo

v ∈ V \{s, t

}, satisfaz a restrição adicional:

Existe conservação de fluxo: O fluxo total que entra num dado nó $v$ é nulo, exceto na fonte, que produz o fluxo, e no sumidouro, que absorve o fluxo. Isto é: $x f (v) = 0$ para todo $v ∈ V \{s, t$ }.

O valor de um possível fluxo de f, denotado $| f |$ , é o fluxo total no sumidouro t da rede de fluxo. Isto é, $| f | = x f (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 \times V \to ℝ \infty$ , 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 $c f$ , é a diferença entre a capacidade do arco e seu fluxo. Isto é, $c f (e) = c (e) - f (e)$ . A partir disso, podemos construir um residual de rede, denotado $G f (V, E f)$ , que modela o montante disponível a capacidade do conjunto de arcos de $G = (V, E)$ . Mais formalmente, dado um rede de fluxo G $G$ , a rede residual $G f$ tem o conjunto de nós V, arco $E f = {e \in E : c f (e) > 0}$ e a capacidade de função $c f$ .

Este conceito é usado no algoritmo de Ford–Fulkerson 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 $(u 1, u 2, ..., u k)$ na rede residual, onde $u 1 = s$ , $u k = t$ , e $c f (u i, u i + 1) > 0$ . Uma rede esta em fluxo máximo se e somente se não há aumentando caminho na rede residual $G f$ .

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 num vértice ligado a cada uma das fontes, com arestas 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]

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.

Abaixo você vê o residual de rede para um determinado fluxo. Observe como há positivos da capacidade residual em algumas arestas, onde a capacidade original é zero, por exemplo, para a aresta . 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
Algoritmo de Edmonds–Karp	1972	$O (m 2 n)$
Algoritmo de MPM (Malhotra, Pramodh-Kumar e Maheshwari)^[4]	1978	$O (n 3)$
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 aresta é . O objetivo é enviar uma determinada quantidade de fluxo da fonte para o receptor, ao menor preço possível.

No problema de circulação, você tem um limite inferior nas arestas, além de o limite superior . Cada aresta 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 aresta em sua extremidade e, então, 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]

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

Paradoxo de Braess
Centralidade
Teoria Constructal
Algoritmo de Ford-Fulkerson
Dinic do algoritmo
Fluxo (redes de computadores)
Grafo de fluxo de
Teorema do fluxo máximo e corte mínimo
Orientado matroid
Problema do caminho mínimo

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

↑ A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989
↑ Black, Paul E. "Supersource" Arquivado em 17 de março de 2016, no Wayback Machine..
↑ Black, Paul E. "Supersink" Arquivado em 17 de março de 2016, no Wayback Machine..
↑ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). «An $O(|V|^{3})$ algorithm for finding maximum flows in networks». Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9
↑ http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf

George T. Heineman; Gary Pollice; Stanley Selkow (2008). «Chapter 8:Network Flow Algorithms». Algorithms in a Nutshell. [S.l.]: Oreilly Media. pp. 226–250. ISBN 978-0-596-51624-6
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. [S.l.]: Prentice Hall. ISBN 0-13-617549-X CS1 maint: Multiple names: authors list (link)
Bollobás, Béla (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. ISBN 3-540-90399-2
Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. ISBN 0-07-557101-3 CS1 maint: Multiple names: authors list (link)
Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. ISBN 0-521-28881-9
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. «26». Introduction to Algorithms 2nd ed. [S.l.]: MIT Press and McGraw-Hill. pp. 696–697. ISBN 0-262-03293-7 CS1 maint: Multiple names: authors list (link)

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

George T. Heineman; Gary Pollice; Stanley Selkow (2008). «Chapter 8:Network Flow Algorithms». Algorithms in a Nutshell. [S.l.]: Oreilly Media. pp. 226–250. ISBN 978-0-596-51624-6
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. [S.l.]: Prentice Hall. ISBN 0-13-617549-X CS1 maint: Multiple names: authors list (link)
Bollobás, Béla (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. ISBN 3-540-90399-2
Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. ISBN 0-07-557101-3 CS1 maint: Multiple names: authors list (link)
Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. ISBN 0-521-28881-9
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. «26». Introduction to Algorithms 2nd ed. [S.l.]: MIT Press and McGraw-Hill. pp. 696–697. ISBN 0-262-03293-7 CS1 maint: Multiple names: authors list (link)

Problema Do Fluxo Máximo
Real gráfico instâncias
Limão biblioteca C++ com vários fluxo máximo e custo mínimo para a circulação de algoritmos
QuickGraph, gráfico de algoritmos e estruturas de dados .Net

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

Problema Do Fluxo Máximo
Real gráfico instâncias
Limão biblioteca C++ com vários fluxo máximo e custo mínimo para a circulação de algoritmos
QuickGraph, gráfico de algoritmos e estruturas de dados .Net

[1] A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

[2] Black, Paul E. "Supersource" Arquivado em 17 de março de 2016, no Wayback Machine..

[3] Black, Paul E. "Supersink" Arquivado em 17 de março de 2016, no Wayback Machine..

[4] Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). «An $O(|V|^{3})$ algorithm for finding maximum flows in networks». Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9

[5] ttp://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf

[1]

[2]

[3]

[4]

[5]