Fluxo em Redes: Definições e Aplicações

Fluxo em Redes Erika Morais Instituto de Informática Universidade Federal de Goiás Fluxo em Redes Definições Uma rede é um grafo orientado G V E em que 1 a cada aresta e E está associado um número real positivo ce denominado capacidade da aresta e 2 há dois vértices especiais e distintos s t V chamados origem e destino respectivamente com as seguintes propriedades A origem s é uma fonte que alcança todos os outros vértices O destino t é um sumidouro alcançado também por todos Fluxo em Redes Definicdes Um fluxo f de s a t em G uma funcdo que associa a cada aresta e E um numero real nao negativo fe satisfazendo as seguintes condicGes 0 fe ce para toda arestae E para todo vértice v st S fwiv S fv Wo 1 we Fluxo na rede O valor do fluxo na origem é denominado valor do fluxo na rede e denotado por fG Fluxo Máximo em Redes O problema de Fluxo Máximo O valor do fluxo em uma rede pode variar de um mínimo igual a zero até um certo máximo O problema do fluxo máximo consiste em dada uma rede determinar o fluxo de valor máximo Fluxo Máximo em Redes Aplicações Escoamento de água de uma origem s a um destino t através de uma rede de tubulação Correntes por redes elétricas Informações por redes de comunicação Fluxo Maximo em Redes Exemplo 1a Um fluxo em rede S say Ae Fluxo Maximo em Redes Exemplo 1b Um fluxo ilegal S Og Fluxo Maximo em Redes Exemplo 1c Um fluxo maximo S Oey Fluxo Máximo em Redes Seja f um fluxo máximo em uma rede GV E 1 Uma aresta e E é saturada quando f e ce 2 Um vértice v V é saturado quando todas as arestas convergentes a v ou todas as arestas divergentes de v estão saturadas 3 Um fluxo é maximal quando todo caminho de s a t em G contém alguma aresta saturada Fluxo Maximo em Redes Exemplo 2a Um fluxo maximal 10 10 NX 11 Ow Fluxo Maximo em Redes Exemplo 2b Um fluxo maximo 11 11 NX 11 Ona Cortes de Fluxo em Redes Definições Seja S V um subconjunto de vértices tal que s S e t S Denote S V S Um corte S S em G é um subconjunto das arestas de G que possuem uma extremidade em S e outra em S Todo caminho da origem s ao destino t em G contém alguma aresta de S S Sejam S S v w E v S e w S S S v w E v S e w S Cortes de Fluxo em Redes Definições Definese capacidade cS S do corte S S como o somatório das capacidades das arestas de S S O corte S S inclui as arestas de S S mas estas não são contadas no cálculo de sua capacidade Um corte mínimo é aquele que possui capacidade mínima Cortes de Fluxo em Redes Fluxo de um corte Seja f um fluxo e S5 um corte em G entao fS5 éo0 fluxo no corte S 5 e é definido como a diferenca FS5 So fle SO Fle eSS eSS Em geral cSS 4 cS5 e fSS 4 fSS Fluxo Maximo em Redes Exemplo 3 Corte 42 oo it ON 30 52 ee Ssab cdt S S s c c b b d a t S S s c b d a t SS c b cS csc cbd ca t 10 S5 fsc fb d fa t Fc b fSS SS 4 Fluxo máximo e corte mínimo Corte x Fluxo O valor do fluxo em uma rede pode ser definido em qualquer corte como indica o lema seguinte Lema 1 Seja f um fluxo em uma rede e S S um corte em G Então f S S f G Fluxo máximo e corte mínimo Definições Uma aresta e tal que ce f e 0 denominase aresta direta É possível que f não seja máximo e não seja possível aumentálo unicamente através de incrementos de fluxos em arestas diretas Há situações em que a única forma de aumentar f consiste em além de incrementar o fluxo em algumas arestas decrementálo em outras Uma aresta e pode receber um decremento de fluxo positivo f e Se f e 0 então e é denominada aresta contrária Fluxo maximo e corte minimo Exemplo 4 Arestas direta e contraria S aay A sa é aresta direta e contraria sc aresta direta sb é aresta contraria Redes residuais Definição Dados um f e G V E a rede residual G f é uma rede com mesmo conjunto de vértices de G e cujas arestas são obtidas pela seguinte contrução 1 Se v w é aresta direta de G então v w é aresta de G também chamada direta e com capacidade cv w cv w f v w 2 Se v w é aresta contrária de G então w v é aresta de G também chamada contrária e com capacidade cw v f v w Redes residuais Definicdo Um caminho de s a t na rede residual Gf denominado aumentante ou caminho de acréscimo de fluxo para f Exemplo 5 G e sua rede residual ay 8 ay 6 uy Ney 10 11 1 a Ore C4 Ocaminho scdabt 6 aumentante Redes residuais Lema 2 Seja f um fluxo em uma rede GV E e G a rede residual correspondente Suponha que exista em G um caminho aumentante v1 v2 vk da origem s v1 ao destino t vk Então f G pode ser aumentado de um valor F mincvj vj1 1 j k Fluxo máximo corte mínimo Teorema 1 O valor do fluxo máximo em uma rede G é igual à capacidade do corte mínimo de G Fluxo máximo corte mínimo Corolário 1 Sejam S S um corte e f um fluxo em uma rede G Então S S é mínimo se e somente se 1 toda aresta e S S estiver saturada e 2 toda aresta e S S satisfizer f e 0 Fluxo máximo corte mínimo Corolário 2 Um fluxo f em uma rede G é máximo se e somente se não existir caminho aumentante para f O algoritmo de FordFulkerson Algoritmo Entrada G s t com capacidades ce inteiras para cada e E 1 F 0 2 para cada aresta e E faça f e 0 3 Construa a rede residual G f 4 enquanto existir caminho v1 vk de s v1 até t vk em G faça 5 F mincvj vj11 j k 6 para j 1 k 1 faça 7 se vj vj1 é aresta direta então 8 f vj vj1 f vj vj1 F 9 senão f vj1 vj f vj1 vj F 10 F F F 11 Construa a rede residual Gf FordFulkerson Dada a rede G V E abaixo utilize o algoritmo de FordFulkerson para encontrar um fluxo maximo de s a t Mostre passo a passo as redes residuais G e os caminhos aumentantes em cada rede residual 16 20 13 Oa Exercicio Para casa Encontre o fluxo maximo na rede G abaixo s fa d ce S t Redes com várias origens e vários depósitos Definição Um problema de fluxo máximo pode ter m origens e n depósitos Este problema pode ser reduzido a um problema de fluxo máximo comum Da seguinte forma 1 Adicionamos uma superorigem s e acrescentamos a ela uma aresta orientada s si com capacidade cs si para cada i 1 2 m 2 Adicionamos um superdepósito t e acrescentamos a ele uma aresta orientada ti t com capacidade cti t para cada i 1 2 n Redes com miltiplos origens e depositos Exemplo 6a Rede com miltiplos origens e depdsitos 51 10 ay a 3 cee S 8 b 6 te a l oS Zoe Kea i a Redes com miltiplas origens e depdsitos Exemplo 6b Rede com miltiplos origens e depositos Or a3 oaec sat CEA ale th Wea 4 eae a Aplicações Fluxo em redes e Emparelhamento O método de FordFulkerson pode ser utilizado para encontrar um emparelhamento máximo em um grafo bipartido não orientado G V E da seguinte forma 1 Construa um fluxo em rede na qual os fluxos equivalem aos emparelhamentos 2 Seja a rede correspondente G V E 3 Encontre um fluxo máximo em G que corresponderá a um emparelhamento máximo em G Aplicações Fluxo em redes e Emparelhamento Construa G V E a partir de G da seguinte forma 1 Sejam a origem s e o destino t novos vértices não pertencentes a V e seja V V s t 2 Se a partição de vértices de G é V X Y as arestas orientadas de G são as arestas de E orientadas de X para Y junto com V novas arestas E s u u X u v u X v Yeu v E v t v Y 3 Atribuimos capacidade unitária a cada aresta em E Fluxo em Rede e Emparelhento maximo Exemplo 7b 2 Exercicio Encontre um emparelhamento maximo em G encontrando um fluxo maximo em G Aplicações Uma comissão bem balanceada O diretor de uma grande universidade com k departamentos acadêmicos deve nomear uma importante comissão Sejam as seguintes restrições 1 Um professor deve ser escolhido de cada departamento 2 Muitos professores estão em dois ou mais departamentos mas um professor não pode representar mais que um departamento 3 Deve haver igual representação entre professores assistentes associados e plenos Considere K divisível por 3 Como a comissão pode ser formada Aplicações Uma comissão bem balanceada 1 Cada departamento professor e categoria deve ser representado por um vértice 2 O vértice s deve enviar uma aresta unitária para cada departamento 3 Cada departamento deve enviar uma aresta unitária para cada professor 4 Cada professor deve enviar uma aresta unitária para cada categoria 5 Cada categoria deve enviar uma aresta de capacidade k3 para o destino t Fluxo em Rede e Emparelhento maximo Exemplo 8 AO Rose SoS REO a me