Baixe o app para aproveitar ainda mais
Prévia do material em texto
Universidade Federal Fluminense Apostila de Pesquisa Operacional II Teoria dos Grafos Lidia Angulo Meza Renato Teixeira da Silva Talita Pereira dos Santos (revisão) Volta Redonda, 11 de março de 2008 (atualizado em 14 de março de 2011) I Sumário 1. Teoria dos Grafos.................................................................................................... 1� 1.1 Histórico ................................................................................................................ 1� 1.2 Conceitos Básicos .................................................................................................. 2� 1.2.1 Grafo ................................................................................................................................ 2� 1.2.2 Adjacência e Incidência ................................................................................................... 3� 1.2.3 Grau de um grafo.............................................................................................................. 3� 1.2.4 Representação de um Grafo ............................................................................................. 4� 1.2.5 Alguns Tipos de Grafos mais Utilizados.......................................................................... 6� 1.2.6 Percursos em Grafos......................................................................................................... 9� 1.3 O Problema do Caminho Mínimo ........................................................................ 9� 1.3.1 Algoritmo de Dijkstra....................................................................................................... 9� 1.3.2 Algoritmo de Floyd ........................................................................................................ 12� 1.3.3 Formulação Matemática do Problema de Caminho Mínimo ......................................... 15� 1.4 O Problema da Árvore Geradora Mínima......................................................... 17� 1.4.1 Conexidade de um grafo ................................................................................................ 17� 1.4.2 Árvore e Árvore Geradora.............................................................................................. 17� 1.4.3 Algoritmo de Prim.......................................................................................................... 18� 1.4.4 Algoritmo de Kruskal..................................................................................................... 18� 1.5 O Problema de Fluxo Máximo............................................................................ 19� 1.5.1 Modelo de Otimização Linear........................................................................................ 19� 1.5.2 Algoritmo de Ford-Fulkerson......................................................................................... 21� 1.6 Bibliografia.......................................................................................................... 26� Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 1 1. Teoria dos Grafos "A inteligência é o farol que nos guia, mas é a vontade que nos faz caminhar." Anônimo 1.1 Histórico Podemos dizer que o estudo sobre grafos iniciou no século XVIII com os estudos de Euler. Ele formulou no ano de 1736 o primeiro problema do que seria chamada posteriormente Teoria dos Grafos a partir de uma questão relevante para arquitetura, mais especificamente ao planejamento urbano. O problema das pontes de Königsberg (atualmente Kaliningrado) na Prússia questionava se existia um caminho em que se pudesse cruzar apenas uma vez cada uma das sete pontes que passam sobre o rio Nagel e ligam duas ilhas centrais, passando pelas quatro áreas e retornando ao ponto de partida. Figura 1.1: Pontes de Königsberg e a representação em grafos Euler construiu um diagrama simplificado onde as ilhas e as margens são representadas por pontos e as pontes pelas linhas que unem esses pontos. Para chegar a conclusão da não existência de solução para esse problema, Euler analisou que para cada ponto da cidade deveria haver uma chegada e uma partida e que elas deveriam ser distintas, pois se deve cruzar uma ponte uma única vez, só havendo rota possível caso o número de ligações recaindo em cada um dos pontos seja constante, fato que não ocorre neste problema. Outro problema que faz parte da história da Teoria dos Grafos é o Problema das Quatro Cores, que buscava determinar o número mínimo de cores necessárias para colorir um mapa de forma que os países com fronteiras comuns tivessem cores diferentes. Francis Guthrie, em 1852, conjecturou que esse número mínimo seria 4. A prova dessa conjectura surgiu somente em 1976 por Appel e Haken. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 2 Em 1856, William R. Hamilton formula um novo problema, o Problema do Ciclo Hamiltoniano. Ele consiste em buscar um caminho que comece e termine num mesmo vértice e passe exatamente uma vez por todos os outros vértices. Esse problema foi precursor do Problema do Caixeiro Viajante, muito abordado atualmente. No século XX houve um maior interesse sobre o estudo da Teoria dos Grafos desencadeando no patamar em que estamos hoje. 1.2 Conceitos Básicos 1.2.1 Grafo Um grafo é uma noção simples e abstrata utilizada para representar a idéia de relação entre "objetos". Graficamente, é representado por uma figura composta de vértices, representando os objetos, que estão unidos por um traço denominado aresta, representando a relação imaginada. Matematicamente, um grafo é representado por: G = (V, A) (1.1) onde V é o conjunto de vértices e A é o conjunto de ligações entre vértices. Grafo Não Orientado Um grafo é dito não orientado quando os pares de vértices não possuem uma ordem, ou seja, quando o par (i, j) é semanticamente igual ao par (j, i), podendo ser expresso como [i, j] onde i, j � V. Figura 1.2: Exemplo de Grafo não orientado Na Figura 1.2, tem-se um exemplo de um grafo não orientado que representa uma rede de computadores em um escritório. A transmissão de dados se dá tanto do computador 1 para o 5 quanto do 5 para o 1. Grafo Orientado (ou Dígrafo) Um grafo é dito orientado quando o sentido das ligações entre os vértices é considerado. Neste caso denomina-se arco o par ordenado (i, j), sendo i o vértice inicial e j o vértice final, onde i, j � V. Quando estes arcos possuem um valor associado, ele é então chamado de rede orientada. A Figura 1.3 mostra um exemplo de rede orientada representando um sistema de transporte, sendo cada vértice uma cidade, cada arco uma estrada ligando uma cidade a outra e o valor associado a cada arco a distância entre cada cidade. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 3 Figura 1.3: Exemplo de Rede Orientada 1.2.2 Adjacência e IncidênciaSejam x e y vértices de um grafo G orientado ou não. Se x e y estão unidos por uma aresta a, então x e y são adjacentes. Além disso, x e y são incidentes em a e a é incidente em x e y. Quando duas arestas compartilham um mesmo vértice, pode-se dizer também que elas são adjacentes. Sejam v e w vértices de um grafo G orientado. Se v e w estão unidos por um arco e, então v e w são adjacentes. Se o arco e começa em v e termina em w então o arco e é incidente de v e incidente a w. Figura 1.4: Adjacência e Incidência num grafo orientado 1.2.3 Grau de um grafo Para grafos não orientados O grau de um vértice x de um grafo F é o número de arestas com incidência em x e representado por d(x). Figura 1.5: Grafo não orientado d(u) = 2, d(v) = 5, d(w) = 4, d(z) = 5 Teorema 1.1. Em qualquer grafo, a soma de todos os graus dos vértices é igual a duas vezes o número de arestas. No exemplo: d(u) + d(v) + d(w) + d(z) = 2 + 5 + 4 + 5 = 16, então o grafo tem 8 arestas. Para grafos orientados Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 4 Seja G um grafo orientado, o grau exterior de um vértice x ou d+(x) é o número de todos os arcos incidentes de x. O grau interior de um vértice x ou d−(x) é o número de todos os arcos incidentes a x. Figura 1.6: Grafo orientado d+(v) = 3, d−(v) = 1, d+(u) = 1, d−(u) = 1, d+(w) = 2, d−(w) = 2, d+(z) = 0, d−(z) = 2 Teorema 1.2. Em um grafo orientado, a soma de todos os graus exteriores e a soma de todos os graus interiores é igual ao número de arcos. No exemplo: d+(v) + d+(u) + d+(w) + d+(z) = 3 + 1 + 2 + 0 = 6 = 1 + 1 + 2 + 2 = d−(v) + d−(u) + d−(w) + d−(z) 1.2.4 Representação de um Grafo A representação gráfica dos vértices e ligações pode ser de fácil visualização, mas não são computacionalmente viáveis. Desta forma, os grafos devem ser representados de forma matemática. Existem várias formas de representar um grafo. Dentre as quais temos: Lista de Adjacências Uma lista de adjacências armazena o relacionamento entre os vértices de um grafo em uma estrutura de listas. Esse tipo de representação é tida como econômica do ponto de vista computacional. Figura 1.7: Exemplo de grafo orientado Vértices Vértices Origem Destino Destino Origem 1 2,3,4 1 - 2 4 2 1 3 - 3 1,4 4 3 4 1,2 Tabela 1.1: Lista de Adjacências Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 5 A Tabela 1.1 apresenta a lista de adjacências do grafo da Figura 1.7. Por se tratar de um grafo orientado, é necessário duas listas de adjacências: uma de origem- destino e outra de destino-origem. Caso se tratasse de um grafo não orientado seria necessário somente a lista de origem-destino. Matriz de Adjacências A matriz de adjacências mostra o relacionamento entre os vértices de um grafo. Ela é uma matriz quadrada de tamanho n, onde n é o número total de vértices. A matriz de adjacências é construída da seguinte forma: ij ij a 1 (i, j) A. M a 0 (i, j) A. = ⇔ ∈�� = � = ⇔ ∉�� (1.2) A partir do grafo utilizado no exemplo anterior (Figura 1.7) foi construída a matriz de adjacências a seguir: 1 2 3 4 1 0 1 1 1 2 0 0 0 1 M 3 0 0 0 0 4 0 0 1 0 � � � � � � = � � � �� � (1.3) onde as linhas representam o vértice de origem e as colunas representam o vértice de destino. Caso i = j e aij = 1, temos o chamado loop, representado pela Figura 1.8. Figura 1.8: Loop Para um grafo não orientado, o procedimento de construção da matriz de adjacências é o mesmo e podemos notar que a matriz gerada é simétrica. Figura 1.9: Exemplo de grafo não orientado Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 6 1 2 3 4 1 0 1 1 0 2 1 0 1 1 M 3 1 1 0 0 4 0 1 0 0 � � � � � � = � � � �� � (1.4) Quando os grafos precisam incluir valores de distâncias, de custos ou outros, estes são representados de forma um pouco diferente. Tem-se uma matriz de adjacências valorada, que é chamada de matriz de distâncias ou custos. A construção dessa matriz se dá da seguinte forma: ij ij ij ij d 0 i j D d c (i, j) A d (i, j) A � = ⇔ = � = = ⇔ ∈� � = ∞ ⇔ ∉� (1.5) Esse tipo de representação será muito utilizado em todas as próximas seções. A Figura 1.10 mostra um exemplo de uma rede orientada e a seguir sua matriz de distâncias ou custos. Figura 1.10: Exemplo de rede orientada 1 2 3 4 1 0 5 6 2 2 0 3 M 3 0 4 5 0 � � � � ∞ ∞� � = � �∞ ∞ ∞ � �� � ∞ ∞ (1.6) 1.2.5 Alguns Tipos de Grafos mais Utilizados Os exemplos aqui citados foram extraídos de BOAVENTURA NETTO (2003). Grafo simétrico Um grafo G = (N,A) será simétrico se (i, j) ∈ A e somente se (j, i) ∈ A, ∀ i, j∈ N. Assim, a matriz de adjacência de G será uma matriz simétrica. Exemplos: Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 7 Figura 1.11: Grafos simétricos Grafo anti-simétrico Se (i, j) ∈ A, um grafo G = (N,A) será anti-simétrico se e somente se (j, i) ∉ A, i, j ∈ N. Claramente, este tipo de relacionamento é utilizado para grafos orientados e não pode possuir laços. Este tipo de grafo pode expressar relações de ordem total ou parcial (paternidade, idade, hierarquia, e outros). Por exemplo, o organograma é um grafo anti- simétrico. Figura 1.12: Grafos anti-simétricos Grafo completo Um grafo G = (N,A) será completo se existir ao menos uma ligação associada a cada par de vértices. No caso orientado, isso significa exatamente uma ligação e, portanto, o grafo possuirá todas as arestas possíveis. São conhecidas como cliques, Kn onde n é o número de vértices do grafo. Figura 1.13: Grafos completos Para o caso orientado, se (i, j) ∉ A então (j, i) ∈ A, isto é, a ausência de um arco em um sentido implicará na presença do arco no sentido oposto. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 8 Grafo Bipartido Aqueles nos quais o conjunto de vértices N pode ser particionado em dois subconjuntos de tal forma que vértices pertencentes a um mesmo subconjunto não são adjacentes. Figura 1.14: Grafo Bipartido Cliques Bipartidas São grafos bipartidos não orientados com o maior número possível de arestas. Denota-se por Kp,q. Figura 1.15: Cliques Bipartidas Grafo Complementar É um grafo G que possui o mesmo conjunto de vértices e as ligações não existentes em umgrafo G = (N,A), sendo que o universo de arcos corresponde às arestas de um clique. Figura 1.16: Grafos Complementares Subgrafo É um grafo que possui o subconjunto de vértices e o subconjunto de ligações de um grafo incidentes aos vértices retirados. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 9 Figura 1.17: Exemplo de subgrafo Grafo Parcial É um grafo obtido pela supressão de ligações do grafo original. Figura 1.18: Grafo Parcial 1.2.6 Percursos em Grafos Um percurso ou itinerário ou ainda cadeia é uma família de ligações sucessivas adjacentes. Um percurso euleriano em um grafo é o percurso que usa cada ligação exatamente uma vez. Um conhecido problema que se encaixa nesse perfil é o Problema do Carteiro Chinês. Nele, o carteiro deseja percorrer todas as ruas da sua rota um número mínimo de vezes e voltar ao correio. Um percurso hamiltoniano em um grafo é o percurso que visita cada vértice uma só vez. No Problema do Caixeiro Viajante, um exemplo que utiliza percurso hamiltoniano, o caixeiro deseja visitar uma variedade de cidades e depois voltar ao ponto de partida. Associando-se o tempo de viagem entre as cidades, o caixeiro planeja um itinerário de tal forma que visite todas as cidades num menor tempo possível. Este é talvez um dos problemas mais estudados na Teoria dos Grafos e de mais difícil solução. Nas seguintes seções estudaremos alguns dos principais problemas em grafos. 1.3 O Problema do Caminho Mínimo O problema do caminho mínimo consiste na minimização do custo de percurso de um grafo entre dois vértices, custo este dado pela soma dos custos de cada aresta percorrida. Para a sua resolução existem vários algoritmos, mas esta disciplina abordará somente dois deles: o Algoritmo de Dijkstra e o Algoritmo de Floyd. 1.3.1 Algoritmo de Dijkstra O Algoritmo de Dijkstra tem por objetivo determinar o caminho mínimo entre uma origem e um destino dados. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 10 Ele será aplicado diretamente sobre o grafo e utilizará a seguinte notação sobre cada vértice: [c, j]X (1.7) onde c representa o custo até o vértice, j representa o vértice precedente e X a classificação do vértice, que pode assumir valores T (temporário) ou P (permanente). Esse algoritmo parte sempre de um vértice T, aquele de menor custo acumulado buscando chegar ao destino. Exemplo: Determine o caminho mínimo entre 1 e 5 da Fig 1.19. Figura 1.19: Rede Orientada do Exemplo Solução: Primeiramente vamos identificar o vértice de origem como um vértice de custo 0, sem precedente e permanente. A seguir vamos identificar os vértices que tem como precedente a origem. Eles serão classificados como temporários. Agora escolheremos o vértice temporário de menor custo c (vértice 3), que será classificado como permanente e repetimos o mesmo processo de identificação dos vértices que o tem como precedente. Esse processo continuará até termos o destino permanente. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 11 Figura 1.20: Solução do Exemplo O caminho mínimo entre os vértices 1 e 5 é {1 − 3 − 5} ou {1 − 3 − 4 − 5} e tem custo de 90un. Ele pode ser visto na Figura 1.20. Exercícios de Fixação - Algoritmo de Dijkstra 1) São obtidas tiras de alumínio de 2cm a partir de outras de 12cm (espessura através de um processo de redução. A Tabela 1.2 descreve o custo de redução para cada 100m de alumínio. Determine a forma mais econômica de se obter tiras de 2cm. 2) Uma empresa está planejando a substituição da sua frota de carros para o período 2006-2011. No início de cada ano toma-se a decisão de se manter a frota operando ou se ela deve ser substituída. Essa substituição pode ocorrer no máximo após três anos de compra da frota. A Tabela 1.3 nos mostra o custo de substituição da frota como função do ano em que ela foi adquirida e o número de anos em operação. Determine o planejamento ótimo para a substituição da frota. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 12 Redução (em cm) Espessura (cm) 2 4 6 12 6,2 7,2 8,5 10 6,8 7,4 9,2 08 7,1 12,8 15,2 06 8,2 14,6 - 04 10,5 - - Tabela 1.2: Custo de Redução Custo de substituição por anos de operação Ano em que a frota foi adquirida 1 2 3 2006 3800 4100 6800 2007 4000 4800 7000 2008 4200 5100 7200 2009 4800 5700 - 2010 5300 - - Tabela 1.3: Custo de substituição da frota 1.3.2 Algoritmo de Floyd Esse algoritmo serve para determinar o caminho mínimo entre todos os pares de vértices. Inicialmente, cria-se uma matriz de distâncias e uma matriz de rotas do grafo seguindo as indicações a seguir: 0 0� = ⇔ � = = ∞ ⇔ ∉� � = ⇔ ∈� ij ij ij ij d i=j D d (i, j) A d c (i, j) A (1.8) 0 0 0 � = � ∞� = � =�� ij ij ij r j d < R r caso contrário. (1.9) onde a matriz D é chamada de matriz de distâncias e R de matriz de rotas realizadas. Em seguida, verifica-se a existência de um caminho de menor custo entre cada par de vértices, ao passar por um vértice intermediário, como na Figura 1.21. Caso exista, altera-se a matriz de distâncias, com esse menor valor e também a matriz de rotas para o vértice intermediário. Num grafo com n vértices, após montar a matriz de distâncias, serão feitas n iterações: • 1ª Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 1 • 2ª Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 2 • ... Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 13 • nª Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice n. Os passos do Algoritmo de Floyd são apresentados a seguir: Figura 1.21: Idéia principal do Algoritmo de Floyd Algorithm 1 Algoritmo de Floyd for k = 1, n do if dik + dkj < dij then dij � dik + dkj rij � rik end if end for Ao executar esse algoritmo deve se atentar para as seguintes observações: • Não é necessário testar nenhum valor da diagonal principal da matriz, pois eles não irão variar; • Na k-ésima iteração, não haverá variação na linha pivô (linha k) e na coluna pivô (coluna k); • Na k-ésima iteração, caso exista na linha pivô (linha k) algum elemento onde dkj = �, então a coluna j não irá variar nessa iteração; • Na k-ésima iteração, caso exista na coluna pivô (coluna k) algum elemento onde dik = �, então a linha i não irá variar nessa iteração. Exemplo: Determine o caminho mínimo entre v5 e v2, v3 e v1 e v4 e v3 da Figura 1.22. Figura 1.22: Rede Orientada do Exemplo Solução: Primeiramente vamos gerar as matrizes de distâncias e de rotas do grafo. Pesquisa Operacional II – Teoria dos GrafosProfª Lidia 14 1 2 3 4 5 1 2 3 4 5 0 1 0 5 3 2 0 3 D 3 0 5 4 1 1 0 1 5 1 1 0 ∞ ∞� � � � ∞ ∞ ∞� � � �= ∞ ∞ ∞ � � ∞� � � � ∞ ∞ 0 1 1 2 0 4 0 2 0 2 3 0 0 R 3 0 0 3 0 5 4 1 2 0 4 5 5 0 2 0 4 5 � � � � � � � �= � � � � � � Por esse ser um grafo com 5 vértices, realizaremos 5 iterações. Iniciaremos agora as iterações, não se esquecendo das observações. k = 1 (para esta iteração, tem-se a linha 1 e a coluna 1 como pivôs) Termo(s) que deve(m) ser analisado(s) nessa iteração: d42 1 2 3 4 5 1 2 3 4 5 1 1 0 5 3 2 0 3 D 3 0 5 4 1 0 1 5 1 1 0 ∞ ∞� � � � ∞ ∞ ∞� � � �= ∞ ∞ ∞ � � ∞� � � � ∞ ∞ 1 1 1 2 0 4 0 2 0 2 3 0 0 R 3 0 0 3 0 5 4 1 0 4 5 5 0 2 0 4 5 � � � � � � � �= � � � � � � • d41 + d12 < d42? 1 + 5 < 1 ? Não 1 2 3 4 5 1 2 3 4 5 1 1 0 5 3 2 0 3 D 3 0 5 4 1 0 1 5 1 1 0 ∞ ∞� � � � ∞ ∞ ∞� � � �= ∞ ∞ ∞ � � ∞� � � � ∞ ∞ 1 1 1 1 2 0 4 0 2 0 2 3 0 0 R 3 0 0 3 0 5 4 1 0 4 5 5 0 2 0 4 5 � � � � � � � �= � � � � � � 2 k = 2 (para esta iteração, tem-se a linha 2 e a coluna 2 como pivôs) Termo(s) que deve(m) ser analisado(s) nessa iteração: d13, d43, d53. 1 2 3 4 5 1 2 3 4 5 2 1 0 5 3 2 0 3 D 3 0 5 4 1 1 0 1 5 1 1 0 ∞� � � � ∞ ∞ ∞� � � �= ∞ ∞ ∞ � � � � � � ∞ 2 1 1 2 4 0 2 0 2 3 0 0 R 3 0 0 3 0 5 4 1 2 4 5 5 0 2 4 5 � � � � � � � �= � � � � � � Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 15 • d12 + d23 < d13? 5 + 3 < �? Sim, então d13 = d12 + d23 = 5 + 3 = 8 r13 = r12 = 2 • d42 + d23 < d43? 1 + 3 < �? Sim, então d43 = d42 + d23 = 1 + 3 = 4 r43 = r42 = 2 • d52 + d23 < d53? 1 + 3 < �? Sim, então d53 = d52 + d23 = 1 + 3 = 4 r53 = r52 = 2 1 2 3 4 5 1 2 3 4 5 2 1 0 5 3 2 0 3 D 3 0 5 4 1 1 0 1 5 1 1 0 ∞� � � � ∞ ∞ ∞� � � �= ∞ ∞ ∞ � � � � � � ∞ 8 4 4 2 1 1 2 4 0 2 0 2 3 0 0 R 3 0 0 3 0 5 4 1 2 4 5 5 0 2 4 5 � � � � � � � �= � � � � � � 2 2 2 Repetiremos esse mesmo processo para k = 3, k = 4 e k = 5, chegando a essas matrizes de distâncias e rotas: 1 2 3 4 5 1 2 3 4 5 5 1 0 4 7 3 4 2 10 0 3 9 8 D 3 7 6 0 6 5 4 1 1 4 0 1 5 2 1 4 1 0 � � � � � � � �= � � � � � � 5 1 1 4 4 4 4 2 3 2 3 3 3 R 3 5 5 3 5 5 4 1 2 2 4 5 5 4 2 2 4 5 � � � � � � � �= � � � � � � • de v5 para v2: 5 − 2, custo = 1 • de v3 para v1: 3 − 5 − 4 − 1, custo = 7 • de v4 para v3: 4 − 2 − 3 custo = 4 1.3.3 Formulação Matemática do Problema de Caminho Mínimo Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 16 Sendo 1 e m os vértices de origem e destino, respectivamente, e cij o custo da ligação (i,j): 1 1 1 1 1 1 . 0 1 1 m m ij ij i= j= m m ij ki j k Min c x , se i S.A x x , se i ou m , se i=m= = =� � − = ≠� � −� � � � � 0 1ij , se (i, j) A x , caso contrário ∉� = � � i, j = 1, 2, 3, ..., m A modelagem do problema terá, portanto variáveis binárias, xij, as quais, ao assumirem o valor 1 indicam que o arco em questão faz parte da rota, e 0, caso contrário. Exemplo: Formular matematicamente o problema de caminho mais curto do grafo da Figura 1.23. Figura 1.23: Grafo do Exemplo Solução: { } 2 7 2 5 4 1 4 3 4 5 1 7 1 1 0,1 OA AD AB OB OC CB CE BE BD DT ED ET OA OB OC DT ET OA AB AD OB AB CB BD BE OC CB CE AD BD ED DT EB CE ED ET ij Min x x x x x x x x x x x x S.A. x x x x x x x x x x x x x x x x x x x x x x x x x i,j + + + + + + + + + + + + + = + = = + + + = + = + + + = + = + ∈ ∀ Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 17 1.4 O Problema da Árvore Geradora Mínima O problema da árvore geradora mínima objetiva encontrar o caminho mais curto de tal maneira que os arcos forneçam um caminho entre todos os pares de vértices. Esse modelo de problema pode ser aplicado a: • Projeto de redes de telecomunicação; • Projeto de redes de transporte (rodovias, ferrovias, etc.); • Projeto de redes de transmissão de energia. Esse tipo de problema é resolvido por vários algoritmos, dentre eles o Algoritmo de Prim e o Algoritmo de Kruskal. Para um melhor entendimento, dois novos conceitos serão apresentados. 1.4.1 Conexidade de um grafo Um grafo é dito conexo se existir pelo menos um percurso entre todos os pares de vértices. Caso contrário, trata-se de um grafo não conexo. Figura 1.24: Conexidade Figura 1.25: Árvore Geradora 1.4.2 Árvore e Árvore Geradora Uma árvore é um grafo conexo e sem ciclos. Uma árvore geradora de um grafo G é um subgrafo de G que inclui cada vértice de G e é uma árvore. Uma árvore possui as seguintes particularidades: • Se a árvore tem n vértices, então ela terá n − 1 arestas; • Caso seja eliminada uma aresta da árvore, teremos um grafo não-conexo; • Caso acrescente uma aresta entre qualquer par de vértices será formado somente um ciclo. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 18 1.4.3 Algoritmo de Prim 1. Selecionar um nó arbitrariamente e ligá-lo ao nó mais próximo; 2. Identificar o nó ainda isolado que esteja mais próximo de um nó já ligado e ligar estes dois nós. Repetir esse passo até que todos os nós estejam ligados entre si. Exemplo: Determine a árvore geradora mínima do grafo da Figura 1.26. Figura 1.26: Grafo do Exemplo Solução: Figura 1.27: Resolução utilizando o Algoritmo de Prim 1.4.4 Algoritmo de Kruskal 1. Ordenar as arestas por ordem crescente de custo, sendo os desempates feitos arbitrariamente, formando uma lista; 2. Selecionar a primeira aresta da lista. Caso gere um ciclo, retirá-la da lista e voltar ao início de 2. Caso contrário, adicioná-la à árvore de suporte e retirá-la da lista. Repetir esse passo até que a árvore de suporte esteja formada. Exemplo: Determine a árvore geradora mínima do grafo do exemplo anterior (Figura 1.26) utilizando o Algoritmo de Kruskal. Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 19 Solução: (B,C) – 1ª aresta adicionada a árvore (D,E) – 2ª aresta adicionada à árvore (O,A) – 3ª aresta adicionada à árvore (A,B) – 4ª aresta adicionada à árvore (B,E) – 5ª aresta adicionada à árvore (O,C) – forma ciclo (B,D)– forma ciclo (C,E) – forma ciclo (O,B) – forma ciclo (D,W) – 6ª aresta adicionada à árvore - Fim (A,D) (E,W) Figura 1.28: Solução do Exemplo 1.5 O Problema de Fluxo Máximo O Problema de Fluxo Máximo objetiva maximizar o fluxo de um ponto de origem (ou fonte) até um ponto de destino (ou sorvedouro) tendo que respeitar as restrições de fluxo de cada arco da rede. Este tipo de problema pode aparecer envolvendo o fluxo de materiais como água, óleo, vapor através de uma rede de tubos; o fluxo máximo de veículos em um sistema de transporte; ou ainda quando se deseja determinar a capacidade máxima de uma linha de produção de um produto que pode ser fabricado utilizando vários roteiros diferentes, passando por vários centros de fabricação, cada um deles com uma certa capacidade instalada. De uma forma geral, seja G(N, A) uma rede orientada onde uij representa a capacidade do arco que liga o vértice i ao vértice j tal que i, j � A. Deseja-se saber qual o número máximo de unidades que podem circular do vértice 1 ao vértice n por unidade de tempo. 1.5.1 Modelo de Otimização Linear Para a formulação desse modelo considera-se existente um arco virtual ligando o nó n ao nó 1 que terá capacidade infinita. Neste arco teremos o fluxo total da rede. Figura 1.29: Exemplo de Arco Virtual Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 20 O modelo matemático será formulado conforme as instruções abaixo: 1Função Objetivo n Max x (1) Restrições 0 1 ∈ ∈ − =� �ij ki (i,j) A (k,i) A SA x x i= , ..., n (2) 0 ≤ ≤ ∀ ∈ij ij x u (i,j) A (3) onde: (1) mostra que se quer maximizar o fluxo entre a fonte e o sorvedouro; (2) faz com que o fluxo que chega em cada nó seja igual ao fluxo que sai do mesmo; e (3) limita o fluxo do arco no intervalo [0, uij], onde uij representa o fluxo máximo do arco que liga os nós i e j. Exemplo: A Companhia Estadual de Gás do Rio de Janeiro (CEG-RJ) deseja determinar a quantidade máxima de metros cúbicos por segundo de gás que pode bombear da estação de Campos para a cidade de Volta Redonda, através de uma rede de gasodutos já existentes. A Figura 1.30 apresenta a atual rede de distribuição de gás da CEG-RJ. Formule um problema de programação linear para este caso. Figura 1.30: Rede de distribuição de gás da CEG-RJ Solução: Primeiramente cria-se o arco virtual. No exemplo em estudo, ele terá fluxo x61. Max x61 SA x61 − (x12 + x13 + x14) = 0 (nó 1) x12 − (x23 + x25 + x26) = 0 (nó 2) x13 + x23 + x43 − (x35) = 0 (nó 3) x14 − (x43 + x45) = 0 (nó 4) x25 + x35 + x45 − (x56) = 0 (nó 5) x26 + x56 − (x61) = 0 (nó 6) 0 � x12 � 15 0 � x13 � 5 0 � x14 � 10 0 � x23 � 8 0 � x25 � 10 0 � x26 � 10 0 � x35 � 10 0 � x43 � 7 0 � x45 � 9 0 � x56 � 15 0 � x61 � 1 Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 21 1.5.2 Algoritmo de Ford-Fulkerson Algoritmo de Ford-Fulkerson simplificado É uma heurística (não garante solução ótima) que funciona pela definição de um caminho de aumento de fluxo num grafo. Caminho de aumento de fluxo é aquele que parte da fonte até o sorvedouro e que apresenta o fluxo de pelo menos um de seus arcos saturado, isto é, utiliza todo o fluxo disponível de pelo menos um arco. Ao acrescentarmos o caminho de aumento ao fluxo já existente no grafo, o fluxo máximo é atingido quando não for possível descobrir mais caminhos de aumento. Para aplicar o Algoritmo de Ford-Fulkerson substituímos o fluxo de cada arco pelo par ordenado (a, b), onde a representa o fluxo disponível no arco e b o fluxo enviado pelo arco. Exemplo: Aplique o Algoritmo de Ford-Fulkerson (heurística) à rede de distribuição de gás da CEG-RJ da Figura 1.30 do exemplo anterior. Solução: Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 22 Figura 1.31: Resolução utilizando o Algoritmo de Ford-Fulkerson (heurística) Como não existe mais nenhum caminho de aumento de fluxo, então o fluxo máximo é igual a 25. Algoritmo de caminhos aumentados Este algoritmo se baseia nos conceitos de rede residual e caminho aumentado. A rede residual mostra as capacidades dos arcos remanescentes, chamadas capacidades residuais, para designar fluxos adicionais. A capacidade residual para o fluxo que vai de um nó a outro é indicada por um número colocado próximo ao nó de origem. Na Figura 1.32, o arco O � B possui capacidade de arco igual a 7, havendo uma capacidade residual de 2 para qualquer designação de fluxo de O para B, e uma capacidade residual de 5 para o fluxo de B para O. Figura 1.32: Capacidade residual de fluxo Quando alguma quantidade de fluxo é designada a um arco, essa quantidade deve ser subtraída da capacidade residual na direção em questão e adicionada à capacidade residual na direção oposta. Um caminho aumentado é um caminho direcionado da origem para o destino de modo que todo arco nesse caminho tenha fluxo residual estritamente positivo. O algoritmo de caminhos aumentados identifica um caminho aumentado na rede, acrescentando a esta um fluxo igual à capacidade residual do caminho selecionado. São realizadas sucessivas iterações até que não exista mais nenhum caminho com fluxo residual positivo, o que indica que a solução atual é ótima (como os caminhos aumentados podem cancelar parte dos fluxos previamente designados na rede original, selecionar os caminhos indiscriminadamente não impede o emprego de uma combinação melhor de designações de fluxo, garantindo que a solução obtida seja ótima). Exemplo: Aplique o Algoritmo de Caminhos Aumentados à rede da Figura 1.33. �� �� �� �� Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 23 O A C B D E T 3 5 4 1 2 4 4 9 6 5 7 1 Figura 1.33: Rede do exemplo Solução: • 1º Caminho: O – B – E – T Capacidade: 5 Fluxo Máximo: 5 O A C B D E T 0 0 4 1 2 4 4 9 5 5 5 1 5 2 0 0 0 0 0 0 3 0 0 1 Figura 1.34: 1º Caminho • 2º Caminho: O – A – D – T Capacidade: 3 Fluxo Máximo: 5 + 3 = 8 O A C B D E T 3 3 4 1 2 4 4 6 5 5 5 1 2 2 0 0 0 0 0 0 0 0 3 1 Figura 1.35: 2º Caminho • 3º Caminho: O – A – B – D – T Capacidade: 1 Fluxo Máximo: 8 + 1 = 9 Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 24 O A C B D E T 3 4 4 0 2 4 3 5 5 5 5 1 1 2 0 0 0 0 1 10 0 4 1 Figura 1.36: 3º Caminho • 4º Caminho: O – B – C – E – T Capacidade: 1 Fluxo Máximo: 9 + 1 = 10 O A C B D E T 3 4 4 0 1 3 3 5 6 5 6 1 1 1 0 1 1 0 1 1 0 0 4 0 Figura 1.37: 4º Caminho • 5º Caminho: O – C – E – D – T Capacidade: 1 Fluxo Máximo: 10 + 1 = 11 O A C B D E T 3 4 3 0 1 2 3 4 6 5 6 0 1 1 1 1 2 0 1 1 0 1 5 0 Figura 1.38: 5º Caminho • 6º Caminho: O – B – D – T Capacidade: 1 Fluxo Máximo: 11 + 1 = 12 Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 25 O A C B D E T 3 4 3 0 1 2 2 3 6 5 7 0 1 0 1 1 2 0 2 1 0 1 6 0 Figura 1.39: 6º Caminho • 7º Caminho: O – C – B – D – T Capacidade: 1 Fluxo Máximo: 12 + 1 = 13 O A C B D E T 3 4 2 0 2 2 1 2 6 5 7 0 1 0 2 0 2 0 3 1 0 1 7 0 Figura 1.40: 7º Caminho • 8º Caminho: O – C – E – B – D – T Capacidade: 1 Fluxo Máximo: 13 + 1 = 14 O A C B D E T 3 4 1 0 2 1 0 1 6 4 7 0 1 0 3 0 3 1 4 1 0 1 8 0 Figura 1.41: 8º Caminho Exercício de Fixação – Algoritmo dos caminhos aumentados 1) Aplique o Algoritmo de Ford-Fulkerson de caminhos aumentados à rede de distribuição de gás da CEG-RJ (Figura 1.30). Pesquisa Operacional II – Teoria dos Grafos Profª Lidia 26 1.6 Bibliografia 1. ALOISE, J.D.; CRUZ, J.S. Teoria dos Grafos e Aplicações. Disponível em: <http://www.dimap.ufrn.br/dario/disciplinas.htm>. Acesso em: 20 jul. 2007. 2. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa Operacional. 1.ed. Rio de janeiro: Editora Campus, 2007. 3. BAAZARA, M.S.; JAVIS, J.J.; SHERALI, H.D. Linear Programming and Network Flows. 2.ed. Nova York: Wiley, 1990. 4. BOAVENTURA NETTO, P.O. Grafos - Teoria, Modelos e Algoritmos. 3.ed., São Paulo: Edgard Blücher Ltda, 2003. 5. FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma Introdução Sucinta à Teoria dos Grafos. Disponível em: <http://www.ime.usp.br/˜pf /teoriadosgrafos/ texto/TeoriaDosGrafos.pdf>. Acesso em: 19 ago. 2007. 6. FERREIRA, J.A.S.; SIMARIA, A.S.A. Algoritmos para a Resolução de Problemas em Redes. Disponível em: <http://www2.egi.ua.pt/cursos/files/SAD/Algoritmos_Redes.pdf>. Acesso em: 14 nov. 2007. 7. GUIMARÃES, J.O. Teoria dos Grafos. Disponível em: <http://www.dc.ufscar.br/ jose/courses/tg.htm>. Acesso em: 20 jul. 2007. 8. LACHTERMACHER,G. Pesquisa Operacional na Tomada de Decisões. 3.ed. Rio de janeiro: Editora Campus, 2007. 9. MARTINS, F.M. Paradigmas da Programação III - Notas de Aula. Disponível em: <http://sim.di.uminho.pt/ ensino2.php3?seccao=geral&id=45>. Acesso em: 20 jul. 2007. 10. MEZA, L.A. Pesquisa Operacional II - Teoria dos Grafos. 2007. 22 f. Notas de Aula. 11. NOGUEIRA, F. Pesquisa Operacional - Notas de Aula. Disponível em: <http://www.engprod.ufjf.br/fernando/epd015/>. Acesso em: 24 nov. 2007. 12. PATRÍCIO, P. Breve introdução à teoria dos grafos. Disponível na internet. Acesso em: 20 jul. 2007. 13. RAGGI, L.A. Teoria e Modelos de Grafos. Disponível em: <http://www.dpi.ufv.br/disciplinas/inf330/index.php?pk=167>. Acesso em: 16 jul. 2007. 14. RIBEIRO, C.C.; ROCHA, C.T. Algoritmos em Grafos. Disponível em: <http://wwwdi.inf.puc-rio.br/ celso/disciplinas.htm>. Acesso em: 21 nov. 2007. 15. SILVA JÚNIOR, E. P. Análise Combinatória e Teoria dos Grafos. Disponível em: <http://www.inf.ufrgs.br/ prestes/disciplinas.html>. Acesso em: 20 jul. 2007. 16. SILVA,M. Grafos - Definições e Conceitos Fundamentais. Disponível em: <http://www.moraissilva.com/grafos_cap1.pdf>. Acesso em: 20 jul. 2007. 17. SOUZA, L. O Teorema das Quatro Cores. Millenium - Revista do ISPV , n.24, p. 125-51, out. 2001. Disponível em: <http://www.ipv.pt/millenium/Millenium24/12.pdf>.
Compartilhar