Projeto e Análise de Algoritmos: Teoria dos Grafos

Projeto e Análise de Algoritmos fatimafigpucminasbr Pontifícia Universidade Católica de Minas Gerais Instituto de Ciências Exatas e Informática Departamento de Ciência da Computação Mestrado em Informática Teoria dos Grafos 2 Conceitos Básicos Deo páginas 1 até 23 mais didático e detalhado Cormen páginas 853 até 861 ou 3 Grafo é uma coleção de vértices e arestas Vértice é um objeto simples que pode ter nomes e outros atributos Aresta é uma conexão entre dois vértices Conceitos Básicos Por definição um grafo deve ter pelo menos 1 vértice e1 V1 V3 e2 V4 e4 e3 e5 V2 4 Grafo da Amizade Modelagem Vértices pessoas Arestas relação de amizade n número de vértices e número de arestas n 4 e 5 5 Problema das Pontes de Königsberg No século XVIII havia na cidade de Königsberg um conjunto de sete pontes que cruzavam o rio Pregel Elas conectavam duas ilhas A e D entre si e as ilhas com as margens B e C Por muito tempo os habitantes daquela cidade perguntavamse se era possível cruzar as sete pontes numa caminhada contínua sem passar duas vezes por qualquer uma delas 6 Problema das Pontes de Königsberg As pontes são identificadas pelas letras de a até g Este problema pode ser representado pelo grafo vértices pontos de terra aresta pontes 7 Problema do Desenho da Casa No desenho abaixo uma criança diz ter posto a ponta do lápis numa das bolinhas e com movimentos contínuos sem levantar e sem retroceder o lápis traçou as linhas que formam o desenho da casa traçando cada linha uma única vez A mãe da criança acha que ela trapaceou pois não foi capaz de achar nenhuma sequência que pudesse produzir tal resultado Você concorda com esta mãe 8 Problema de Transporte Nos problemas que envolvem transportes de carga ou pessoas os pontos de parada embarque e desembarque são os vértices e as estradas entre os pontos são as arestas 9 Problema de Transporte Problema de Conectividade dadas as direções das vias é possível ir da cidade A até a cidade B sem andar na contramão Problema de Fluxo Máximo dada a capacidade de fluxo em cada via qual é a quantidade de mercadoria que podemos mandar de uma cidade A a uma cidade B Problema de Menor Caminho Dados os comprimentos de cada via qual o percurso mais rápido para sair de uma cidade A e chegar a uma cidade B 10 Grafo não orientado GVEé um par onde V é um conjunto finito e o conjunto de arestas E consiste em pares de vértices não orientados A aresta vivj e vjvi são consideradas a mesma aresta Terminologia V1 V2 V3 V4 V5 e1 e2 e3 e4 e5 e9 e8 e7 e6 11 Terminologia Grafo orientado G é um par VE onde V é um conjunto finito e E é uma relação binária em V V1 V2 V3 V4 V5 e1 e2 e3 e4 e5 e9 e8 e7 e6 12 Terminologia Autoloop uma aresta associada ao par de vértices vivi Arestas paralelas quando mais de uma aresta está associada ao mesmo par de vértices Grafo simples um grafo que não possui autoloops nem arestas paralelas grafo simples e3 e3 é um autoloop e1 e2 e1 e e2 são arestas paralelas 13 Terminologia Se uv é uma aresta em um grafo GVE dizemos que o vértice v é adjacente ao vértice u em grafo não orientado a relação de adjacência é simétrica Se uv é uma aresta de um grafo orientado e vu não é uma aresta dizemos que o vértice v é adjacente ao vértice u mas u não é adjacente a v Se uv é uma aresta em um grafo orientado GVE dizemos que a aresta uv é incidente do ou sai do vértice u e é incidente no ou entra no vértice v Se uv é uma aresta em um grafo não orientado GVE dizemos que a aresta uv é incidente nos vértices u e v 14 Terminologia O grau de um vértice em um grafo não orientado é o número de arestas incidentes nele Em um grafo orientado o grau de saída de um vértice é o número de arestas que saem dele e o grau de entrada de um vértice é o número de arestas que entram nele O grau de um vértice em um grafo orientado é seu grau de entrada somado a seu grau de saída grau do vértice 2 é 4 grau de entrada do vértice 5 é 2 grau de saída do vértice 5 é 1 15 Terminologia Um grafo no qual todos os vértices possuem o mesmo grau é chamado de grafo regular Um vértice com nenhuma aresta incidente é chamado de vértice isolado Um vértice com grau 1 é chamado de vértice pendente Um grafo sem nenhuma aresta é chamado de grafo nulo todos os vértices em um grafo nulo são vértices isolados grafo regular 5 é um vértice isolado 1 é um vértice pendente grafo nulo 16 Terminologia Um grafo não orientado GVE é um grafo completo se para cada par de vértices vi e vj existe uma aresta entre vi e vj Em um grafo completo quaisquer dois vértices distintos são adjacentes Kn K1 K2 K3 K4 K5 K6 K7 K8 17 Terminologia Um caminho de comprimento k de um vértice u até um vértice u em um grafo GVE é uma sequência V0V1V2Vk de vértices tais que uV0 uVk e Vi1Vi E para i12k O comprimento de um caminho é o número de arestas no caminho Se existe um caminho de u até u dizemos que u é acessível a partir de u Um caminho simples é aquele em que todos os vértices no caminho são distintos 145 é um caminho simples 125366 não é um caminho simples 18 Terminologia Um caminho V0V1V2Vk forma um ciclo se V0Vk e o caminho contém pelo menos uma aresta Ciclo simples é um ciclo no qual os vértices V1V2Vk são distintos Um autoloop é um ciclo de comprimento 1 Um grafo sem ciclos é acíclico 4123524 é um ciclo 12541 é um ciclo simples 19 Terminologia Um grafo não orientado é conectado se todo par de vértices está conectado por um caminho Cada um dos subgrafos conectados é chamado de componente Os componentes conexos de um grafo são as classes de equivalência de vértices sob a relação é acessível a partir de grafo não conectado com 5 componentes 20 Terminologia Um grafo orientado é fortemente conectado se cada um de dois vértices quaisquer é acessível a partir do outro Os componentes fortemente conectados de um grafo orientado são as classes de equivalência de vértices sob a relação são mutuamente acessíveis grafo possui 3 componentes fortemente conectados 21 Terminologia Grafo complementar seja G VE um grafo simples O complemento de G é um grafo formado da seguinte maneira Os vértices de são todos os vértices de G As arestas de são exatamente as arestas que faltam em G para formarmos um grafo completo G 22 Terminologia Um grafo bipartido é um grafo não orientado GVE em que V pode ser particionado em dois conjuntos V1 e V2 tais que uvE implica que uV1 e vV2 ou uV2 e vV1 Em um grafo bipartido todas as arestas ligam um vértice do conjunto V1 com um vértice do conjunto V2 a b c d e 23 Terminologia Dois grafos G e H são ditos isomorfos se existe uma correspondência umparaum entre seus vértices e entre suas arestas de maneira que as relações de incidência são preservadas Condições necessárias mas não suficientes para que G e H sejam isomorfos mesmo número de vértices e mesmo número de arestas mesmo número de componentes mesmo número de vértices com o mesmo grau a b c d e 1 2 3 4 5 a b c d e f 1 2 3 4 5 6 24 Propriedades A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G O número de vértices de grau ímpar em um grafo é par 25 Propriedades O número mínimo de arestas de um grafo simples com n vértices e k componentes é nk O número máximo de arestas de um grafo simples com n vértices e k componentes é Grafo simples e conexo k1 Grafo simples 26 Exercícios 1 Todos os grafos abaixo são isomorfos exceto d b c e a 27 Exercícios 2 Com relação ao grafo completo Kn responda a Qual é o grau dos seus vértices b Quantas arestas ele possui 3 Encontre um grafo com 5 vértices que seja isomorfo a seu complemento 4 Qual o número de arestas de um grafo que é isomorfo a seu complemento 28 Exercícios 5 Com relação ao grafo abaixo responda a O grafo é simples b Completo c Regular d Conectado e Encontre 2 caminhos simples entre V3 e V6 f Encontre 1 ciclo g Indique uma aresta cuja remoção tornará o grafo não conectado v3 v4 v5 v7 v6 v2 v1 29 Estruturas de Dados Cormen páginas 419 até 422 30 Matriz de Adjacências A matriz de adjacências de um grafo simples G com n vértices é uma matriz n x n definida como Mij 1 se existe uma aresta entre os vértices i e j Mij 0 caso contrário Vantagem verificar adjacência é O1 31 Lista de Adjacências Consiste de uma lista para cada vértice do grafo contendo todos os vértices adjacentes a ele Armazena apenas os elementos diferentes de zero da matriz de adjacências Desvantagem para encontrar se um vértice é adjacente a outro devemos percorrer uma lista encadeada 32 Estruturas de Dados para Dígrafos grafos orientados Lista de Adjacências Matriz de Adjacências 33 Algoritmos Elementares em Grafos Cormen páginas 422 até 444 34 Algoritmos Elementares em Grafos Busca em Largura ou Busca em Amplitude Breadth First Busca em Profundidade Depth First Número de Componentes de um Grafo Ordenação Topológica Componentes Fortemente Conectados 35 Busca em Largura Dado um grafo GVE e um vértice de origem s a busca em largura explora sistematicamente as arestas de G até descobrir cada vértice acessível a partir de s Calcula a distância menor número de arestas desde s até todos os vértices acessíveis a partir de s Visita todos os vértices à distância k a partir de s antes de visitar quaisquer vértices à distância k1 36 Busca em Largura du distância desde a origem s até o vértice u πu predecessor de u se u não tem predecessor πu NIL Adju conjunto de vértices adjacentes a u coloru cor do vértice u pode assumir os seguintes valores branco vértices não visitados cor inicial de todos os vértices cinza vértices visitados que possuem vizinhos visitados e não visitados preto vértices visitados que possuem apenas vizinhos visitados cor final de todos os vértices 37 Busca em Largura Mostre s Mostre v 38 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 0 Q Saída do Mostre s e Mostre v V1 V1 39 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 1 1 Q Saída do Mostre s e Mostre v V1 V2 V3 0 V2 V3 40 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 1 2 2 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 0 1 V3 V5 V6 41 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 2 2 2 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 0 1 1 V5 V6 V4 42 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 3 2 2 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 V7 0 1 1 2 V6 V4 V7 43 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 3 2 3 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 V7 V8 0 1 1 2 2 V4 V7 V8 44 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 3 2 3 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 V7 V8 0 1 1 2 2 V7 V8 45 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 3 2 3 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 V7 V8 V8 0 1 1 2 2 46 Busca em Largura V2 V5 V3 V1 V4 V6 V7 V8 3 2 3 Q Saída do Mostre s e Mostre v V1 V2 V3 V5 V6 V4 V7 V8 0 1 1 2 2 47 Busca em Largura Análise de Complexidade Cada vértice de V é colocado na fila Q no máximo uma vez OV A lista de adjacência de um vértice qualquer de u é percorrida somente quando o vértice é removido da fila A soma de todas as listas de adjacentes é OE então o tempo total gasto com as listas de adjacentes é OE Enfileirar e desenfileirar tem custo O1 Complexidade OV E 48 Busca em Profundidade Utiliza a estratégia de procurar mais fundo no grafo sempre que possível As arestas são exploradas a partir do vértice v mais recentemente visitado que ainda tem arestas inexploradas saindo dele Quando todas as arestas de v são exploradas a busca regressa para explorar as arestas que deixam o vértice a partir do qual v foi visitado Esse processo continua até que visitamos todos os vértices acessíveis a partir do vértice de origem inicial 49 Busca em Profundidade du registra quando u é visitado pela primeira vez fu registra quando a busca termina de examinar a lista de adjacências de u πu predecessor de u se u não tem predecessor πu NIL Adju conjunto de vértices adjacentes a u coloru cor do vértice u pode assumir os seguintes valores branco vértices não visitados cor inicial de todos os vértices cinza vértices visitados cuja lista de adjacência não foi completamente examinada preto vértices visitados cuja lista de adjacência foi completamente examinada cor final de todos os vértices 50 Busca em Profundidade Mostre u 51 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 Saída do Mostre u V1 52 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 Saída do Mostre u V1 V2 53 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 Saída do Mostre u V1 V2 V5 54 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 4 Saída do Mostre u V1 V2 V5 V6 55 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 4 5 Saída do Mostre u V1 V2 V5 V6 V7 56 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 4 5 6 Saída do Mostre u V1 V2 V5 V6 V7 V8 57 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 4 5 67 Saída do Mostre u V1 V2 V5 V6 V7 V8 58 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 4 58 67 67 Saída do Mostre u V1 V2 V5 V6 V7 V8 59 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 3 49 58 67 67 Saída do Mostre u V1 V2 V5 V6 V7 V8 60 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 2 310 49 58 67 67 Saída do Mostre u V1 V2 V5 V6 V7 V8 61 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 211 310 49 58 67 67 Saída do Mostre u V1 V2 V5 V6 V7 V8 62 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 211 310 49 58 67 67 12 Saída do Mostre u V1 V2 V5 V6 V7 V8 V3 63 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 211 310 49 58 67 67 12 13 Saída do Mostre u V1 V2 V5 V6 V7 V8 V3 V4 64 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 211 310 49 58 67 67 12 1314 Saída do Mostre u V1 V2 V5 V6 V7 V8 V3 V4 65 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 1 211 310 49 58 67 67 1215 1314 Saída do Mostre u V1 V2 V5 V6 V7 V8 V3 V4 66 Busca em Profundidade V2 V5 V3 V1 V4 V6 V7 V8 116 211 310 49 58 67 67 1215 1314 Saída do Mostre u V1 V2 V5 V6 V7 V8 V3 V4 67 Busca em Profundidade Análise de Complexidade considerando matriz de adjacências O loop inicial é On O procedimento DFSVISIT é chamado exatamente uma vez para cada vértice do grafo pois ele é invocado somente sobre vértices brancos e a primeira ação é pintar o vértice de cinza Durante a execução de DFSVISIT o loop das linhas 4 a 7 é executado n vezes Portanto o tempo de execução total é On On2 On2 68 Número de Componentes de um Grafo Como encontrar o número de componentes de um grafo grafo com 5 componentes 69 Número de Componentes de um Grafo k 0 A variável k armazenará o número de componentes do grafo G k k1 Mostre k 70 Ordenação Topológica A busca em profundidade pode ser usada para executar ordenações topológicas em grafos acíclicos orientados gaos Uma ordenação topológica de um gaos GVE é uma ordenação linear de todos os seus vértices tal que se G contém uma aresta uv então u aparece antes de v na ordenação Se o grafo não é acíclico então não é possível nenhuma ordenação linear Uma ordenação topológica de um grafo pode ser vista como uma ordenação de seus vértices ao longo de uma linha horizontal de tal forma que todas as arestas orientadas sigam da esquerda para a direita 71 Ordenação Topológica Grafos acíclicos orientados são usados em muitas aplicações para indicar precedência entre eventos Como exemplo considere o grafo que surge quando o professor Bumstead se veste pela manhã 72 Ordenação Topológica Uma aresta orientada uv no gao indica que a peça de roupa u deve ser vestida antes da peça v Uma ordenação topológica desse gao fornece uma ordem para o processo de se vestir 73 Ordenação Topológica Algoritmo a seguir ordena topologicamente um gao Os vértices topologicamente ordenados aparecem na ordem inversa de seus tempos de término 74 Ordenação Topológica Análise de complexidade A busca em profundidade é On2 e leva o tempo O1 para inserir cada um dos n vértices à frente da lista encadeada Portanto a ordenação topológica tem complexidade de tempo de On2 Componentes Fortemente Conectados 76 Componentes Fortemente Conectados A busca em profundidade pode ser utilizada também para realizar a decomposição de um grafo orientado em seus componentes fortemente conectados A transposta de um grafo GVE é um grafo GTVET onde ET consiste nas arestas de G com seus sentidos invertidos G GT 77 Componentes Fortemente Conectados Algoritmo a seguir calcula os componentes fortemente conectados de um grafo orientado GVE usando duas pesquisas primeiro na profundidade uma sobre G e uma sobre GT Como abordagem inicial o método para encontrar as SCCs de um grafo consiste em a partir de cada vértice vV realizar uma DFS para encontrar todos os vértices uV tal que existe vu Depois iniciamos o conjunto de SCCs com um SCC para cada vértice v do grafo Finalmente para cada par de vértices uvV tal que existem vu e uv determinamos que uv pertencem ao mesmo SCC Nota se existem vu e uv por transitividade fazemos SCCv SCCu SCCv SCCu pseudocódigo findSCCQuadracticG acha os SCCs do grafo G passo 1 para cada vértice v pertencente a V fazer DFS em G a partir de v marcando vértice u visitado como alcançável a partir de v passo 2 para cada vértice v pertencente a V fazer criar um conjunto UnionFind contendo apenas v representando uma SCC passo 3 para cada vértice v pertencente a V fazer para cada vértice u marcado como alcançável a partir de v fazer se v também for alcançável a partir de u fazer unir conjuntos UnionFind de u e de v 78 79 Componentes Fortemente Conectados Grafo orientado G Grafo GT Grafo de componentes acíclicos obtido pela condensação de cada componente fortemente conectado de G de modo que apenas um único vértice permaneça em cada componente 80 Componentes Fortemente Conectados Análise de Complexidade Busca em profundidade sobre G On2 Cálculo de GT On2 Busca em profundidade sobre GT On2 Portanto a complexidade de tempo é On2 On2 On2 On2 81 Grafos Eulerianos Grafos Unicursais Problema do Carteiro Chinês Deo páginas 42 até 60 82 Problema das Pontes de Königsberg No século XVIII Königsberg era a capital da Prússia Oriental A cidade foi construída à volta do rio Pregel e para unir todas as partes da cidade foram construídas 7 pontes Os habitantes da cidade gostavam de passear pelas pontes e tentavam encontrar uma forma de atravessar todas as pontes exatamente uma vez e retornar ao ponto inicial 83 Problema das Pontes de Königsberg vértices pontos de terra aresta pontes 84 Problema das Pontes de Königsberg Em 1736 Euler mostrou que existe um caminho com ponto de início em qualquer vértice que passa através de cada aresta exatamente uma vez e termina no vértice inicial se e somente se todos os vértices tiverem grau par O grafo que não cumprir com essas condições não é Euleriano No exemplo da ponte todos os quatro vértices têm grau ímpar logo não é possível atravessar todas as pontes exatamente uma vez e retornar ao ponto inicial 85 Grafos Eulerianos Problema encontrar um ciclo que passe por todas as arestas uma única vez Se é possível encontrar um ciclo que passe por todas as arestas uma única vez dizemos que G é um grafo euleriano TEOREMA Um grafo é euleriano se e somente se todos os seus vértices tiverem grau par 86 Mapa do Departamento de Matemática A figura abaixo ilustra o mapa do Departamento de Matemática de uma importante Universidade A entrada principal está na parte norte do Departamento Determine se é possível que uma pessoa possa andar pelo Departamento passando através de cada porta exatamente uma vez e terminando onde começou 87 O Problema do Explorador Um explorador deseja explorar todas as estradas entre um número de cidades É possível encontrar um roteiro que passe por cada estrada apenas uma vez e volte a cidade inicial vértices cidades aresta estradas 88 Problema do Dominó É possível arranjar todas as peças de um dominó em um caminho fechado 89 Grafos Eulerianos Análise de Complexidade Para verificar se um grafo é euleriano basta verificar o grau de todos os vértices do grafo Para verificar o grau de um vértice temos que percorrer uma linha da matriz de adjacências que tem tamanho n Como são n vértices a complexidade é On2 90 Grafos Unicursais Um grafo G é dito unicursal se ele possuir um caminho aberto de Euler ou seja se é possível percorrer todas as arestas de G apenas uma vez sem retornar ao vértice inicial Caminho de Euler a c d a b d e b Se adicionarmos uma aresta entre os vértices inicial e final do caminho aberto de Euler esse grafo passa a ser um grafo euleriano a b c d e 91 Grafos Unicursais Um grafo conexo é unicursal se e somente se ele possuir exatamente 2 vértices de grau ímpar TEOREMA Em um grafo conexo G com exatamente 2K vértices de grau ímpar existem K subgrafos disjuntos de arestas todos eles unicursais de maneira que juntos eles contêm todas as arestas de G Casos Grafo euleriano todos os vértices de grau par Grafo unicursal dois vértices de grau ímpar Grafo qualquer 2K vértices de grau ímpar ktraçável 92 Carteiro Chinês Um carteiro deseja entregar cartas ao longo de todas as ruas de uma cidade e retornar ao ponto inicial Como ele pode planejar as rotas de forma a percorrer a menor distância possível Se o grafo for euleriano basta percorrer o ciclo de Euler Caso contrário algumas arestas serão percorridas mais de uma vez 1 2 3 4 2 3 6 2 5 a b c d v w 93 Exercícios 6 Para quais valores de a e b o grafo abaixo é euleriano 7 Determine os valores de n para os quais o grafo completo Kn é euleriano Para quais valores de n o Kn é unicursal Justifique b vértices a vértices 94 Exercícios 8 Para o grafo do problema das pontes de Königsberg qual é o menor número de pontes que devem ser removidas para que o grafo resultante seja unicursal Quais pontes Idem para Euleriano 9 É possível visitar todas as salas passando por todas as portas exatamente uma vez e retornando ao ponto inicial