Fluxo em Redes: Definições e Propriedades

261 Fluxo em redes Nesta seção daremos uma definição da teoria de grafos para o fluxo em redes discutiremos suas propriedades e definiremos com exatidão o problema de fluxo máximo Introduziremos também algumas regras úteis de notação Fluxo em redes e fluxos Um fluxo em rede G V E é um grafo orientado em que cada aresta u v E tem uma capacidade não negativa cu v 0 Se u v E supomos que cu v 0 Distinguir nos vértices em um fluxo em rede uma origem s e um sorvedor t Por conveniência supondo que cada vértice reside em algum caminho desde a origem até o sorvedor Isto é para todo vértice v V existe um caminho s v t Então o grafo é conectado e E V 1 A Figura 261 mostra um exemplo de um fluxo em rede Agora estamos prontos para definir fluxos de modo mais formal Seja G V E um fluxo em rede com uma função de capacidade c Seja s a origem da rede e seja t o sorvedor Um fluxo em G é uma função de valor real f V V R que satisfaça as três propriedades seguintes Restrição de capacidade Para todo u v V exigimos fu v cu v Antisimetria oblíqua Para todo u v V exigimos fu v fv u Conservação de fluxo Para todo u V s t exigimos vV fu v 0 A quantidade fu v que pode ser positiva 0 ou negativa é chamada fluxo do vértice u até o vértice v O valor de um fluxo f é definido como f s v E ou seja o fluxo total que sai da origem Aqui a notação denota valor de fluxo e não valor absoluto ou cardinalidade No problema de fluxo máximo temos um fluxo em rede G com origem s e sorvedor t e desejamos encontrar um fluxo de valor máximo Antes de ver um exemplo de um problema de fluxo em rede vamos explorar brevemente as três propriedades de fluxo A restrição de capacidade simplesmente afirma que o fluxo de um vértice aut outro não deve exceder a capacidade dada A antisimetria é uma conveniência de notação que afirma que o fluxo de um vértice u até um vértice v é o valor negativo do fluxo no sentido inverso A propriedade de conservação de fluxo afirma que o fluxo total para fora de um vértice que não seja a origem ou o sorvedor é 0 Por antisimetria podemos reescrever a propriedade de conservação de fluxo como fu v 0 para todo u V s t Isto é o fluxo total em um vértice é 0 Quando um u v nem u u está em E então não pode haver nenhum fluxo entre u e v e fu v fv u 0 O Exercício 2611 lhe pede para provar formalmente essa propriedade Nossas última observação a respeito das propriedades de fluxo lida com fluxos que são positivos O fluxo total positivo que entra em um vértice v é definido por fu v com fu v 0 FIGURA 261 a Um fluxo em rede G V E para o problema de transporte da Lucky Puck Company A fábrica de Vancouver é a origem s e o armazém de Winnipeg é o sorvedor t Os discos para hóquei são transportados por cidades intermediárias mas apenas cu v caixotes por dia podem ir da cidade u para a cidade v Cada aresta é identificada com sua capacidade b Um fluxo f em G com valor f 19 São mostrados apenas fluxos positivos Se fu v 0 a aresta u v é identificada por fu vu v A notação de barra é usada apenas para separar o fluxo e a capacidade ela não indica a operação de divisão Se fu v 0 a aresta u v é identificada apenas por sua capacidade O fluxo total positivo que sai de um vértice é definido de forma simétrica Definimos o fluxo total líquido como um vértice como o fluxo total positivo que sai de um vértice menos o fluxo total positivo que entra em um vértice Uma interpretação da propriedade de conservação de fluxo é que o fluxo total positivo que entra em outro vértice que não a origem ou o sorvedor deve ser igual ao fluxo total positivo que sai desse vértice Essa propriedade de que o fluxo total líquido de um vértice deve ser igual 0 é referenciada com frequência de modo informal como o fluxo que entra é igual ao fluxo que sai Um exemplo de fluxo Um fluxo em rede pode modelar o problema de transporte mostrado na Figura 261a A Lucky Puck Company tem uma fábrica origem s em Vancouver que produz discos para hóquei e tem um armazém sorvedor t em Winnipeg que os mantém em estoque A Lucky Puck aluga espaço em caminhos de outra firma para transportar os discos da fábrica até o armazém Pelo fato de que caminhos viajam por rotas especificadas arestas entre cidades vértices e possuem uma capacidade limitada a Lucky Puck pode transportar no máximo cu v caixotes por dia entre cada par de cidades u e v na figura 261a A Lucky Puck não tem nenhum controle sobre essas rotas e capacidades e assim não pode alterar o fluxo em rede mostrado na Figura 261a Sua meta é determinar o maior número de caixotes por dia que podem ser transportados e depois produzirem essa quantidade pois não há nenhum sentido em produzir mais discos do que é possível transportar para o armazém A Lucky Puck não está preocupada com o tempo que leva um determinado disco para ir da fábrica ao armazém a empresa se preocupa em fazer p caixotes por dia saírem da fábrica e p caixotes por dia chegarem ao armazém À primeira vista parece apropriado modelar o fluxo de remessas com um fluxo nessa rede porque o número de caixotes transportados por dia de uma cidade para outra está sujeito a uma restrição de capacidade Além disso a conservação de fluxo deve ser obedecida de modo que em um estado constante a taxa na qual os discos entram em uma cidade intermediária tem de ser igual à taxa em que eles saem da cidade Caso contrário os caixotes se acumulariam em cidades intermediárias Porém há uma sutil diferença entre remessas e fluxos A Lucky Puck pode transportar discos de Edmonton para Calgary e 3 caixotes de Calgary para Edmonton quando seria possível obter o mesmo efeito líquido transportando 5 caixotes de Edmonton para Calgary e 0 caixotes de Calgary para Edmonton É presumivelmente reinvenção nos processos Representamos esse último exemplo com um fluxo termos fv1 v2 5 e fv2 v1 5 Na realidade 3 dos 8 caixotes por dia de v1 para v2 são cancelados por 3 caixotes por dia de v2 para v1 Em geral o cancelamento nos permite representar as remessas entre duas cidades por um fluxo que é positivo ao longo do máximo uma das duas arestas entre os vértices correspondentes Ou seja qualquer situação na qual os discos são transportados em ambos os sentidos em duas cidades pode ser transformada com o uso do cancelamento em uma situação equivalente na qual os discos são transportados somente em um sentido o sentido de fluxo positivo Dado um fluxo f que surgiu de digamos remessas físicas não podemos reconstruir as remessas exatas Se soubermos que fu v 5 esse fluxo pode ocorrer porque 5 unidades transportadas de u para v ou porque 8 unidades foram transportadas de u para v e 3 unidades foram transportadas de v para u Em geral não nos preocuparíamos com o fluxo como as remessas físicas reais estão configuradas para qualquer par de vértices não nos preocuparíamos com a quantidade que influi que traça entre eles Se nos preocuparmos com as remessas subjacentes então devemos usar um modelo diferente um modelo que retenha informações sobre remessas em ambos os sentidos A Lucky Puck pode perceber que é inútil transportar 8 caixotes por dia de Edmonton para Calgary e 3 caixotes de Calgary para Edmonton quando seria possível obter o mesmo efeito líquido transportando 5 caixotes de Edmonton para Calgary e 0 caixotes de Calgary para Edmonton É presumivelmente reinvenção nos processos Representamos esse último exemplo com um fluxo termos fv1 v2 5 e fv2 v1 5 Na realidade 3 dos 8 caixotes por dia de v1 para v2 são cancelados por 3 caixotes por dia de v2 para v1 Em geral o cancelamento nos permite representar as remessas entre duas cidades por um fluxo que é positivo ao longo do máximo uma das duas arestas entre os vértices correspondentes Ou seja qualquer situação na qual os discos são transportados em ambos os sentidos em duas cidades pode ser transformada com o uso do cancelamento em uma situação equivalente na qual os discos são transportados somente em um sentido o sentido de fluxo positivo Dado um fluxo f que surgiu de digamos remessas físicas não podemos reconstruir as remessas exatas Se soubermos que fu v 5 esse fluxo pode ocorrer porque 5 unidades transportadas de u para v ou porque 8 unidades foram transportadas de u para v e 3 unidades foram transportadas de v para u Em geral não nos preocuparíamos com o fluxo como as remessas físicas reais estão configuradas para qualquer par de vértices não nos preocuparíamos com a quantidade que influi que traça entre eles Se nos preocuparmos com as remessas subjacentes então devemos usar um modelo diferente um modelo que retenha informações sobre remessas em ambos os sentidos Redes com várias origens e vários sorvedores Um problema de fluxo máximo pode ter várias origens e vários sorvedores em vez de apenas uma unidade de cada Por exemplo a Lucky Puck Company poderia na realidade ter um conjunto de n fábricas s1 s2 sm e um conjunto de n armazéns t1 t2 tn como mostra a Figura 262a Felizmente esse problema não é mais difícil que o fluxo máximo comum Podemos reduzir o problema de determinar um fluxo máximo em uma rede com várias origens e vários sorvedores a um problema de fluxo máximo comum A Figura 262b mostra como a rede de a pode ser convertida em um fluxo em rede comum com apenas uma única origem e um único sorvedor Adicionamos uma superorigem s e acrescentamos a ela uma aresta orientada s si com capacidade cs si 0 para cada i 1 2 m Também criamos um novo super sorvedor t e acrescentamos a ele uma aresta orientada ti t com capacidade cti t 0 para cada i 1 2 n Intuitivamente qualquer fluxo na rede em a corresponde a um fluxo na rede em b e viceversa A origem única e simplesmente fornece tanto fluxo quanto necessário para as várias origens si e o único sorvedor t consome igualmente tanto fluxo quanto necessários para os vários sorvedores ti O Exercício 2613 lhe pede para provar formalmente que os dois problemas são equivalentes Como utilizar fluxos Vamos lidar com diversas funções como f que utilizamos como argumentos dois vértices em um fluxo em rede Neste capítulo utilizaremos uma notação de somatório implícito na qual qualquer argumento em ambos pode ser um conjunto de vértices com a interpretação que o valor denotado é a soma de todos os modos possíveis de substituir os argumentos por seus parâmetros Por exemplo se X e Y são conjuntos de vértices então fX Y xXyY fx y FIGURA 262 Convertendo um problema de fluxo máximo de várias origens e vários servidores em um problema com uma única origem e um único servidor a Um fluxo em rede com cinco origens S s1 s2 s3 s4 s5 e três servidores T t1 t2 t3 b Um fluxo em rede equivalente de origem única e servidor único Adicionamos uma superorigem s e uma aresta com capacidade infinita desde s até cada uma das várias origens Adicionamos também um superdepósito t e uma aresta com capacidade infinita de cada um dos vários depósitos até t Portanto a restrição de conservação de fluxo pode ser expressa como a condição de que u V 0 para todo u V s t Além disso por conveniência em geral omitiremos as chaves de conjuntos quando elas tiverem de ser usadas de modo diferente na notação de somatório implícita Por exemplo na equação fs V s fs V a expressão V s significa o conjunto V s A notação de conjuntos implícitos frequentemente simplifica equações envolvendo fluxos O lema a seguir cuja prova fica para o Exercício 2614 capta várias das identidades de ocorrências mais comuns que envolvem fluxos e a notação de conjuntos implícitos 261 Prove que o fluxo total em um rede G V E e o fluxo f mostrados na Figura 261b encontre um par de subconjuntos X Y V para o qual fX Y fV X Y Em seguida encontre um par de subconjuntos X Y V para o qual fX Y fV X Y f fu v fu v fu v fu v fu v fu v fu v f fu v No caso das restrições de capacidade observe que fu v cu v para todo u v V Pela equação 265 temos então f fu v fu v fu v fu v ccu v fu v cu v No caso da conservação de fluxo observe que para todo u V s t temos vV f fu v vV fu v fu v 0 vV fu v 0 Finalmente temos f f vV f fs v vV fs v fs v vV fs v vV fs v f f Caminhos aumentantes Dados um fluxo em rede G V E e um fluxo f um caminho aumentante p é um caminho simples desde s até t na rede residual Gf Pela definição de rede residual cada aresta u v em um caminho aumentante admite algum fluxo positivo adicional de u até v sem violar a restrição de capacidade sobre a aresta O caminho sombreado na Figura 263b é um caminho aumentante Tratando a rede residual Gf na figura como um fluxo em rede podemos transportar até 4 unidades de fluxo adicional por cada aresta desse caminho sem violar uma restrição de capacidade pois a menor capacidade residual nesse caminho é cv2 v3 4 Chamamos a quantidade máxima pela qual podemos aumentar o fluxo em cada aresta de um caminho aumentante p de capacidade residual de p dada por cp mincu v u v está em p FIGURA 263 a O fluxo em rede G e o fluxo f da Figura 261b b A rede residual Gf com o caminho aumentante p sombrado sua capacidade residual é cp cv2 v3 4 c O fluxo em G que resulta da ampliação ao longo do caminho p por sua capacidade residual 4 d A rede residual induzida pelo fluxo em c FIGURA 264 Um corte S T no fluxo em rede da Figura 261b onde S s v1 v2 e T v3 v4 t Os vértices em S são pretos e os vértices em T são brancos O fluxo líquido por S T é fS T 19 e a capacidade é cS T 26 Teorema 267 Teorema de fluxo máximo e corte mínimo Se f é um fluxo em rede G V E com origem s e sorvedouro t então as condições a seguir são equivalentes 1 f é um fluxo máximo em G 2 A rede residual Gf não contém nenhum caminho aumentante 3 f cS T para algum corte S T de G O algoritmo básico de FordFulkerson Em cada iteração do método de FordFulkerson encontramos algum caminho aumentante p e aumentamos o fluxo f em cada aresta de p pela capacidade residual cp A implementação do método a seguir calcula o fluxo máximo em um grafo G V E atualizando o fluxo fu v em cada par u v de vértices que estão conectados por uma aresta 1 for cada aresta u v 2 do fu v 0 3 fv u 0 FIGURA 265 A execução do algoritmo básico de FordFulkerson ad Iterações sucessivas do loop while O lado esquerdo de cada parte mostra a rede residual Gf da linha 4 com um caminho aumentante sombreado p O lado direito de cada parte mostra o novo fluxo f que resulta da adição de fp à rede residual em a é a rede de entrada G e A rede residual no último teste do loop while Ela não tem nenhum caminho aumentante e o fluxo f mostrado em d é então um fluxo máximo O algoritmo de EdmondsKarp Teorema 269 Se o algoritmo de EdmondsKarp é executado em um fluxo em rede G V E com origem s e sorvedor t então o número total de ampliações de fluxo executadas pelo algoritmo é no máximo OVE Exercícios 2621 Na Figura 261b qual é o fluxo pelo corte s v2 v3 v1 v3 t Qual é a capacidade desse corte 2622 Mostre a execução do algoritmo de EdmondsKarp sobre o fluxo em rede da Figura 261a 2623 No exemplo da Figura 266 qual é o corte mínimo correspondente ao fluxo máximo mostrado Dos caminhos em ampliação que aparecem no exemplo quais são os dois que cancelam o fluxo 2624 Prove que para qualquer par de vértices u e v e quaisquer funções de capacidade e de fluxo c e f temos cu v cv u cu v cv u 2625 Lembrese de que a construção na Seção 261 que converte um fluxo em rede de várias origens e vários servidores em uma rede de origem única e servidor único adiciona arestas com capacidade infinita Prove que qualquer fluxo na rede resultante tem um valor finito se as arestas da rede original de várias origens e vários servidores têm capacidade finita 2626 Suponha que cada origem s em um problema de várias origens e vários servidores produza exatamente pi unidades de fluxo de modo que fsb V pi Suponha também que cada servidor tj consome exatamente qj unidades de forma que fV tj qj onde Σ pi Σ qj Mostre como converter o problema de encontrar um fluxoque obedeça a essas restrições adicionais no problema de fluxo máximo em um fluxo em rede de origem única e servidor único 2627 Prove o Lema 263 2628 Mostre que um fluxo máximo em uma rede G V E sempre pode ser encontrado por uma sequência de no máximo E caminhos em ampliação Sugestão Determine os caminhos depois de encontrar o fluxo máximo 2629 A conectividade de aresta de um grafo não orientado é o número mínimo k de arestas que devem ser removidas para desconectar o grafo Por exemplo a conectividade de aresta de uma árvore é 1 e a conectividade de aresta de uma cadeia cíclica de vértices é 2 Mostre como a conectividade de aresta de um grafo não orientado G V E pode ser determinada pela execução de um algoritmo de fluxo máximo sobre no máximo V fluxos em rede cada um com OE arestas 26210 Suponha que um fluxo em rede G V E tem arestas simétricas isto é u v E se e somente se v u E Mostre que o algoritmo de EdmondsKarp termina depois de no máximo V E4 iterações Sugestão Para qualquer aresta u v considere a maneira como os u e ov t mudam entre os momentos nos quais u v é crítica O problema do emparelhamento bipartido máximo Dado um grafo não orientado G V E um emparelhamento é um subconjunto de arestas M E tais que para todos os vértices v V no máximo uma aresta de M é incidente sobre v Dizemos que um vértice v V corresponde pelo emparelhamento M se alguma aresta em M é incidente sobre v caso contrário v não é correspondido Um emparelhamento máximo é um emparelhamento de cardinalidade máxima ou seja um emparelhamento M tal que para qualquer emparelhamento M temos M M Nesta seção vamos restringir nossa atenção à localização de emparelhamentos máximos em grafos bipartidos Suponhamos que o conjunto de vértices pode ser particionado em V L R onde L e R são disjuntos e todas as arestas em E passam entre L e R Vamos supor ainda que todo vértice em V tem pelo menos uma aresta incidente A Figura 267 ilustra a noção de um emparelhamento O fluxo em rede correspondente a um grafo bipartido a O grafo bipartido G V E com partição de vértices V L R da Figura 267 Um emparelhamento máximo é mostrado por arestas sombreadas b O fluxo em rede correspondente G com um fluxo máximo mostrado Cada aresta tem capacidade unitária Arestas sombreadas têm um fluxo igual a 1 e todas as outras arestas não conduzem nenhum fluxo As arestas sombreadas de L também equivalem às arestas de um emparelhamento máximo do grafo bipartido uma unidade de fluxo positivo pela conservação de fluxo uma unidade de fluxo positivo deve sair Além disso tendo em vista que f tem valor inteiro para cada u L a única unidade de fluxo pode entrar em no máximo uma aresta e pode sair no máximo de uma aresta Desse modo uma unidade de fluxo positivo entra em u se somente se existe exatamente um vértice v R tal que fu v 1 e no máximo uma aresta que sai de cada u e L transporta fluxo positivo Um argumento simétrico pode ser criado para cada v R O conjunto M é então um emparelhamento Para verificar que M I observe que para todo vértice correspondente a u L temos fu v 1 para toda aresta u v E M temos fu v 0 Consequentemente M fL R fV fL L fL t pelo Lema 261 Podemos simplificar consideravelmente a expressão anterior A conservação de fluxo implica que fL V 0 o Lema 261 implica que fL L 0 a antisimetria implica que fL s fs L e como não existe nenhuma aresta de L para t temos fL t 0 Desse modo M fL s fV s pois todas as arestas que saem de s vão para L I pela definição de I Com base no Lema 2610 gostaríamos de concluir que um emparelhamento máximo em um grafo bipartido G equivale a um fluxo máximo em seu fluxo em rede correspondente G e podemos então calcular uma comparação máxima em G executando um algoritmo de fluxo máximo em G O único senão nesse raciocínio é que o algoritmo de fluxo máximo poderia retornar um fluxo G para o qual algfu v não é um inteiro ainda que o valor de fluxo f tenha de ser um inteiro O teorema aqui mostra que se usarmos o método de FordFulkerson essa diferença não pode surgir Teorema 2611 Teorema de integralidade Se a função de capacidade c utiliza apenas valores inteiros então o fluxo máximo produzido pelo método FordFulkerson apresenta a propriedade de que f tem valor inteiro Além disso para todos os vértices u e v o valor de fu v é um inteiro Prova A prova é por indução sobre o número de iterações Vamos deixar à prova do Exercício 2632 Agora podemos provar o corolário a seguir para o Lema 2610 Corolário 2612 A cardinalidade de um emparelhamento máximo em um grafo bipartido G é igual ao valor de um fluxo máximo f em seu fluxo em rede correspondente G Prova Usamos a nomenclatura do Lema 2610 Suponha que M seja um emparelhamento máximo em G e que o fluxo correspondente f em G não seja máximo Então existe um fluxo máximo m em G tal que P I Tendo em vista que as capacidades em G são valores inteiros pelo Teorema 261 podemos supor que f tem valor inteiro Desse modo f equivale a um emparelhamento M em G com cardinalidade M P I M contradizendo nossa hipótese de que M é um emparelhamento máximo De modo semelhante podemos mostrar que se f for um fluxo máximo em G seu emparelhamento equivalente será um emparelhamento máximo em G Portanto dado um grafo bipartido não orientado G podemos encontrar um emparelhamento máximo criando o fluxo em rede G executando o método de FordFulkerson e obtendo direta