Coloração de Mapas e Representação de Grafos

DAOO DESENVOLVIMENTO DE APLICAGOES ORIENTADAS A OBJETOS Grafos 1 Motivagao 1 Motivagao 2 Definigdes Qual é o numero minimo de cores necessarias para colorir um mapa qualquer de tal forma que paises vizinhos com cperases Sobre erates fronteira comum de extensdo 0 tenham cores diferentes A Figura 1 ilustra uma possivel situagado em que sdo 5 Busca em Grafos necessarias 4 cores para colorir os paises Qualquer quinto pais adicionado a figura pode ser colorido com a cor verde Representagves de Grafos em C Fechamento Transitivo pois nado fara fronteira com o pais do centro A 8 Algoritmo do Menor Caminho 9 O Problema da Maximizagao do Fluxo FIGURA 1 Coloragao de Mapas Sera que vocé consegue desenhar um mapa em que sdo necessarias mais do que 4 cores para colorilo mantendo paises vizinhos com cores diferentes Para responder formalmente a pergunta provando qual é o numero minimo de cores precisamos modelar o problema usando uma estrutura de dados conhecida como GRAFO 2 Definigdes x 21 Grafo Um grafo consiste em e um conjunto de nos ou vértices e e umconjunto de arcos ou arestas definidos através de um par de nos 22 Representacdo grafica Exemplo de um grafo Conjunto de vértices ou nés V A B C D E F G H e Conjunto de arestas A AB AD AC AA CD CF EG FIGURA 2 Exemplo de um grafo No grafo da figura acima cada aresta é formada por um par nao ordenado de vértices ou seja AB é equivalente a BA por exemplo No entanto se o conjunto A de arestas for formado de pares ordenados entdo 0 grafo é chamado grafo direcionado ou orientado ou digrafo e as arestas neste caso sdo representadas graficamente por setas Quando o grafo é direcionado A B ndo é equivalente a B A Exemplo FIGURA 3 Um grafo direcionado ou dígrafo Nós V A B C D E F G H Arcos A AA AB AC AD CD CF EG Uma árvore é sempre um grafo mas um grafo pode não ser uma árvore 23 Termos importantes Um nó n é incidente a um arco x se x é um dos dois nós no par ordenado que define x O arco é também dito incidente aos nós que o compõem No grafo da Figura 3 o vértice C é incidente às arestas AC CD e CF e a aresta EG também é dita incidente aos nós E e G O grau de um nó é o número de arcos incidentes a ele O grau do nó C é 3 pois aparece em 3 arcos AC CD e CF O grau de entrada de um nó n é o número de arcos que têm n como segundo nó do par ordenado Grau de saída primeiro nó do par ordenado O grau de saída do nó C é 2 pois aparece em primeiro lugar em 2 arestas CD e CF Já o seu grau de entrada é 1 Um nó n é adjacente a um nó m se existe um arco de m para n No grafo da Figura 3 G é adjacente a E mas E não é adjacente a G Se n é adjacente a m n é chamado de sucessor de m e m é o predecessor de n 24 Relações Grafos permitem expressar relações entre elementos Uma relação R sobre um conjunto V é um conjunto de pares ordenados de elementos de V Exemplo de uma relação grafo V 3 5 6 8 10 17 R 310 56 58 617 817 1017 Se xy pertence a R dizemos que x está relacionado a y em R No exemplo acima x está relacionado a y se x y e além disso yx2 1 ou seja o resto da divisão de y por x é ímpar Ou seja a relação R pode ser assim definida Esta relação R pode ser representada através do grafo R x y x y V x y yx2 1 5S 19 7 8 417 1 5 FIGURA 4 Um grafo é uma emrelagdoem entre pares de nds Podemos associar um valor etiqueta a cada arco de um grafo por exemplo o valor de y x na figura acima Um grafo no qual um valor pode ser numero string etc 6 associado a cada arco é chamado grafo com peso ou rede O valor associado a aresta é chamado peso nz uneab adiciona um arco entre os nds ae b se ja nado existe uneabp adiciona arco com peso p entre os nds ae b remvab remove arco deaab se ele existe adjacenteab V true se 6 for adjacente a a F false caso contrario Para simplificar V true e F false em todo o texto abaixo nz Um caminho em um grafo é uma sequéncia de vértices conectados por arestas Mais formalmente um caminho de comprimento k de um néd aaumno b em um grafo é uma sequéncia de k 1 nds ny ng Mp1 tais que M1 be e adjacentenni41 V Vi 1k Exemplo de um caminho No grafo da figura abaixo um caminho de comprimento 4 de AaD éADECD FIGURA 5 Um grafo com ciclos Um caminho de um no para ele mesmo é chamado ciclo Um grafo direcionado contendo ciclos 6 chamado ciclico caso contrario 6 chamado aciclico Um grafo direcionado aciclico 6 chamado DAG Directed Acyclic Graph Exemplo de um ciclo No grafo do exemplo anterior 6 um ciclo o caminho DECD nz Ha duas maneiras distintas de se percorrer um grafo a partir de um determinado vértice vp 1 Busca em Largura e 2 Busca em Profundidade Para grafos o mais comum é usar o termo busca ao invés de percurso pois normalmente o grafo é percorrido para buscar um determinado elemento Quando o grafo nao é conexo precisamos escolher um vg diferente para cada componente conexa do grafo 51 Busca em Largura Corresponde a percorrer o grafo a partir de um vértice em círculos concêntricos veja Figura FIGURA 6 Exemplo de Busca em largura Começamos visitando o vértice Em seguida identificamos todos os vértices adjacentes a e os visitamos Depois identificamos os vértices adjacentes aos adjacentes e os visitamos e assim por diante até que todos os nós sejam visitados Precisamos marcar os vértices já visitados de forma a que o algoritmo não entre em loop Para tanto atribuímos a cada vértice 3 possíveis estados nãovisitado identificado e visitado Algoritmo Inicialmente todos os vértices estão não visitados Sendo o vértice inicial e uma fila 1 marque v como identificado e o insira em f 2 enquanto f não estiver vazia 21 remova de f um vértice u 22 visite u 23 marque u como visitado 24 para cada vértice v adjacente a u faça 241 se v é nãovisitado 2411 marque v como identificado e o insira em f O conteúdo da fila após a visita de cada nó do grafo acima ficará vértice sendo visitado conteúdo de após a visita de 0 1 2 3 4 5 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 6 7 8 9 10 7 8 9 10 8 9 10 9 10 10 52 Busca em Profundidade No percurso em profundidade o nó é inicialmente visitado Na sequência um nó adjacente a ele é escolhido e visitado Este procedimento prossegue até não ser mais possível prosseguir Neste caso retorna a um nó anterior e verifica se existe algum outro nó adjacente não visitado prosseguindo a partir dali ou retornando a um nó anterior Cada vértice pode estar em um dos 3 possíveis estados abaixo v0 v0 0 v0 v0 v0 f 0 f u u f u v0 nãovisitado sendovisitado e visitado Algoritmo Inicialmente todos os vértices estão não visitados Sendo o vértice inicial 1 visite v 2 marque v como sendovisitado 3 para cada vértice v adjacente a v faça 31 se v for nãovisitado 311 recursivamente comece o algoritmo com v sendo v 4 marque v como visitado A figura abaixo mostra o percurso em profundidade seguido e os estados dos vértices até chegarem no vértice 9 sendo FIGURA 7 Percurso em profundidade Neste caso os vértices serão visitados na seguinte ordem considerando a ordem de marcação sendovisitado 0 1 2 3 8 9 4 5 7 10 6 Já a ordem em que os nós são marcados visitados é 8 7 10 5 4 9 3 6 2 1 0 1 Exercício Considere o grafo da figura abaixo e determine a ordem em que os nós são visitados quando for percorrido a em largura e b em profundidade em b considere a ordem em que são marcados sendovisitados e visitados FIGURA 8 Em que ordem os vértices deste grafo são visitados 6 Representações de Grafos em C v0 0 0 0 0 0 v0 0 Sendo No numero de nés de um grafo podemos considerar os nds de um grafo como sendo numerados de até N1 Se necessario podemos ter uma tabela de simbolos para mapear o numero do nd em uma informagao de um tipo qualquer TipoDado nele armazenada como ilustrado na figura abaixo A o CE Beli C4 ela So FIGURA 9 Uso de uma tabela auxiliar para mapear a informagado do no em indice de 0 a codeNcode1 Afim de representar um grafo basta verificar a existéncia de arcos entre os nos inicialmente sem considerar a possibilidade de os arcos terem pesos associados Existem essencialmente dois tipos de representagao de grafos 1 por Lista de Adjacéncias 2 por Matriz de Adjacéncias 61 Lista de Adjacéncias Nesta representagao mantemos para cada vértice a do grafo uma lista ligada de vértices v tais que a uj A Para o grafo da Figura 5 precisamos armazenar a seguinte estrutura 2 3 12 2 3 3 4 4 2 3 Para implementar isso em C podemos usar por exemplo um vetor de listas ligadas struct No int vertice No prox ti No grafoN Note que grafo é um vetor de N posigdées que representam os N vértices Cada posido corresponde a um ponteiro para o primeiro no de uma lista ligada contendo os vértices que sao adjacentes a ele Exemplo 2 es ole a 2fetofsod fae fer sla To ale FIGURA 10 Exemplo de uma lista de adjacéncias de um grafo com 5 nos Alternativamente podese usar a classe vector no lugar da lista ligada da biblioteca padrao C std vectorint grafoN Exercicio Implemente a classe Grafo definida anteriormente usando a representagao por lista de adjacéncias 62 Matriz de Adjacéncias A outra forma de representar que utilizaremos em seguida é por meio de uma matriz booleana bool adjNJN onde adjij true se existe arco entre o nó i e o nó j e adjij false caso contrário Esta matriz é chamada matriz adjacência ou matriz de adjacências e descreve completamente um grafo com N nós true V e false F Exemplo de uma matriz adjacência FIGURA 11 Exemplo de uma matriz adjacência de um grafo com 5 nós A classe Grafo com seus métodos pode ser então implementada tendo a matriz adj como um de seus atributos Embora o número máximo de nós do grafo seja limitado por MAXNOS o número real de nós N é dado no momento da instanciação dos objetos da classe isto é como parâmetro do construtor constexpr unsigned int MAXNOS 100 número máximo de nós no grafo class Grafo private bool adjMAXNOSMAXNOS int N número de nós no grafo MAXNOS public Grafoint numnos construtor void une int a int b void remvint a int b bool adjacenteint a int b auxiliar void imprime imprime matriz adjacencia na tela Implementação da operação une void Grafouneint a int b if a0 aN b0 bN a e b são válidos adjab true No caso de grafos com peso a classe pode ser definida por Grafo adj matrizbool MAXNOSxMAXNOS false peso matrizfloat MAXNOSxMAXNOS N int Grafonumnos int uneaint bint p float remvaint bint adjacenteaint bint bool pesoaint bint float imprime Note que o tipo do peso não precisa necessariamente ser float Os tipos das informações guardadas nos vértices e do peso dependem do problema a resolver 3 Exercício Termine a implementação em C das demais operações sobre grafos sem e com peso No caso de termos grafos com peso basta que cada elemento da matriz seja uma estrutura com dois campos adj indicando se existe ou não arco e peso indicando o peso do arco caso ele exista typedef struct bool adj int peso Arco Arco adjpesoNN Outra opção é definir duas matrizes NxN adj e peso FIGURA 12 Representação de um grafo com peso Obviamente existem outras formas de se representar grafos em C por exemplo com cada nó contendo uma lista ligada de ponteiros para os seus sucessores um bom exercício de programação No entanto ficarmos aqui com a representação por matrizes que nos permitirá diretamente calcular o seu Fechamento Transitivo 7 Fechamento Transitivo A matriz de adjacências adj descreve completamente um grafo Assim se adjik adjkj V então existe um caminho de comprimento 2 de i a j passando por k FIGURA 13 Representação de um grafo com peso Se a expressão lógica abaixo for verdadeira adji0 adj0j adji1 adj1j adjiN1 adjN1j V então existe algum caminho de comprimento 2 entre i e j passando por algum nó Considere então a matriz adj como sendo formada por adj ij adji0 adj0j adji1 adj1j adjiN1 adjN1j adj é chamada matriz caminho de comprimento 2 e adj ij indica se existe um caminho de comprimento exatamente igual a 2 de i a j No exemplo anterior adj corresponde a 0 1 2 3 4 0 F F F V V 1 F F F V V 2 F F F V V 3 F F F V F 4 F F F F V adj pode no entanto ser calculada como sendo o resultado de adj x adj produto booleano onde multiplicação corresponde a e lógico e soma a ou lógico Mais genericamente Para saber se existe no dígrafo um caminho de comprimento menor ou igual a 3 entre os nós i e j basta verificar se a expressão abaixo é verdadeira adjij adj ij adj ij Chamamos de Fechamento Transitivo ou Matriz Caminho de um grafo com N vértices a matriz cujos elementos indicam se existe algum caminho de qualquer comprimento entre 2 de seus vértices Ou seja caminhoij V se existe algum caminho de qualquer comprimento entre os nós i e j 2 2 2 2 2 2 adj adj x adj k k1 2 3 Os elementos da matriz caminho são definidos por Note que Basta irmos até adj mesmo que existam caminhos de tamanho M N Isto porque se existe um caminho de i a j de comprimento M existirá também pelo menos um outro caminho de comprimento menor ou igual a N pois se o caminho tem comprimento maior do que o número de nós certamente ele contém ciclos que podem ser todos removidos A matriz caminho do exemplo anterior é então definida como sendo caminho adj adj adj adj adj FIGURA 14 O fechamento transitivo ou matriz caminho de um grafo A matriz caminho é chamada FECHAMENTO TRANSITIVO da matriz adj 8 O Algoritmo do Menor Caminho Dijkstra Considere o problema de encontrar o menor caminho entre dois vértices s e t em um grafo com peso No exemplo da figura abaixo s 0 e t 5 FIGURA 15 Exemplo de grafo para encontrar o menor caminho de S a T Neste exemplo Menor distância 9 Menor caminho 0 2 1 4 5 Eis o algoritmo para encontrar a menor distância e o menor caminho entre dois nós s e t em um grafo direcionado também conhecido como algoritmo de Dijkstra em homenagem ao seu criador 81 Dados MAXNOS número máximo de nós no grafo N número de nós no grafo com peso INFINITO número muito grande maior que qualquer distância possível pesoij distância 0 de i a j se adjacenteij true INFINITO caso contrário distanciai menor distância calculada até o momento de s a i calculadoi true ou false para indicar se distanciai contém ou não a menor distância possível de s a i corrente nó cuja menor distância de s foi calculada mais recentemente precedei nó que precede i no menor caminho encontrado até então A nova distância a ser testada é calculada a partir da distância de s até o nó corrente somada do peso das próximas arestas como ilustrado na figura abaixo caminhoij adjij adj ij adj ij 2 N N 2 3 4 5 FIGURA 16 Nova distância 4 Exercício Adicionar o método pesoij na classe Grafo definida anteriormente Será necessário definir como atributo da classe uma outra matriz além da adj para armazenar os pesos dos arcos 82 Algoritmo int GrafoMenorCaminhoint s int t int precede int distanciaMAXNOS bool calculadoMAXNOS for i0 iN i distanciai INFINITO calculadoi false distancias 0 calculados true corrente s while corrente t int menordist INFINITO menor das novas distâncias calculadas int k próximo corrente aquele com menor distância int dc distanciacorrente distância calculada de s até o nó corrente for int i0 iN i if calculadoi int novadist dc pesocorrentei if novadist distanciai distanciai novadist precedei corrente if distanciai menordist menordist distanciai k i se já calculado não faz nada fim do for corrente k calculadocorrente true return distanciat Clique na figura abaixo para ver o algoritmo em ação tecle s para recomeçar Desenvolvimento de Aplicações Orientadas a Objetos Prof Luiz A de P Lima Jr Observações Ao implementar o algoritmo acima cuide para que x INFINITO INFINITO para qualquer valor de x No grafo da Figura 8 com s 0 e t 5 o vetor precede de 6 posições 6 é número de vértices será preenchido da seguinte forma 2 0 1 4 onde significa valor não utilizado devendo ser interpretado da seguinte forma começando na posição t5 o que vem antes do 5 no menor caminho é o 4 o que vem antes do 4 é o 1 e assim por diante até chegar em 0 que é o s Projeto Menor Distância entre 2 Cidades Implemente um programa que dado um grafo com peso composto de nomes de cidades e distâncias entre elas calcule a menor distância e o menor caminho entre duas cidades quaisquer solicitadas pelo usuário Adicional se for um grafo direcionado como saber se existe um caminho entre 2 nós 9 O Problema da Maximização do Fluxo extra Se o grafo abaixo representa o modelo de um sistema hidráulico onde os arcos representam tubulações os nós junções do sistema hidráulico os números a capacidade das tubulações em litrossegundo o problema do fluxo consiste em maximizar a quantidade de água fluindo de S a T A água circula numa única direção nas tubulações Embora S seja capaz de produzir água em alta taxa e T seja capaz de consumila em taxa comparável o sistema hidráulico pode não ser capaz de levála da origem ao destino FIGURA 17 Problema da maximização do fluxo Problemas similares rede elétrica rede ferroviária rede de comunicação ou qualquer outro sistema de distribuição no qual desejese maximizar a quantidade de algo sendo entregue de um ponto a outro 91 A Função Capacidade 92 A Função Fluxo Propriedades para todos nós do grafo sendo xy pertencentes ao conjunto de nós do grafo Ou seja a quantidade de água saindo de S por todas as tubulações tem que ser igual à quantidade de água chegando em T por todas as tubulações para todo y pertecente ao conjunto dos nós e para todo Ou seja a quantidade de água saindo de um nó deve ser igual à quantidade de água chegando àquele nó ca b capacidade da conexão de a até b se adjacentea b V 0 caso contrário fa b fluxo de a até b se adjacentea b V 0 caso contrário fa b 0 fa b ca b fS x fy T v fx y fy z x S e y T Método para Calculo da Fungdo Fluxo Otima que maximiza v 1 Achar caminho de S a T no qual o fluxo possa ser aumentado por ser menor do que a capacidade k 2 No grafo ao lado se os fluxos entre S e Y e entre X e T podem ser aumentados de k e se fXY pode ser reduzido de k k entdo esta operacdo pode ser feita mantendose as propriedades acima e aumentando o fluxo total v k Exemplo FIGURA 18 Caso especial 33 44 53 51 63 43 44 v7 FIGURA 19 Resultado do fluxo maximo possivel v7 2021 Luiz A de P Lima Jr