Projeto e Análise de Algoritmos: Grafos Hamiltonianos e Problemas Relacionados

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 Parte 2 2 Grafos Hamiltonianos Passeio do Cavalo Problema do Caixeiro Viajante Deo páginas 30 até 35 3 Grafos Hamiltonianos Um ciclo de Hamilton em um grafo conexo é um ciclo simples que passa por todos os vértices do grafo uma única vez Todo grafo que possui um ciclo de hamilton é chamado de grafo hamiltoniano O ciclo de hamilton de um grafo com n vértices contém n arestas 4 Grafos Hamiltonianos Um caminho de Hamilton em um grafo conexo é um caminho que passa por todos os vértices do grafo exatamente uma vez 5 Grafos Hamiltonianos Considerações sobre grafos Hamiltonianos O grafo deve ser conexo Autoloops e arestas paralelas podem ser desconsideradas Se um grafo é hamiltoniano então a inclusão de qualquer aresta não atrapalha esta condição Análise de Complexidade Para verificar se existe um ciclo de hamilton em um grafo conexo devemos tentar todas as possibilidades ou seja devemos gerar todas as permutações nos n vértices Portanto a complexidade do problema é On 6 Exercícios 10 Os seguintes grafos são hamiltonianos a b c d e 7 Passeio do Cavalo Um cavalo do xadrez deve começar em alguma posição visitar todas as posições exatamente uma vez e retornar à posição inicial Precisamos encontrar um ciclo hamiltoniano para responder à questão 8 Problema do Caixeiro Viajante Um caixeiro viajante deseja visitar um número de cidades e voltar ao ponto de origem de maneira que ele visite todas as cidades e percorra a menor distância possível Como escolher sua rota grafo com peso nas arestas Vértices cidades Arestas estradas Encontrar um ciclo de hamilton de peso mínimo A E B C D 9 6 8 7 3 2 5 8 3 6 9 Problema do Caixeiro Viajante Um viajante deve visitar clientes instalados em 6 cidades da Península Ibérica Procurase determinar qual o menor percurso de forma que o visitante comece em uma cidade passe por todas as cidades e termine na cidade de origem Problema do Caixeiro Viajante 11 Problema do Caixeiro Viajante Análise de Complexidade A solução mais direta é gerar todas as permutações e verificar qual é a que possui o menor comprimento Como o número de permutações é n esta solução tem complexidade On 12 Árvores Árvores Geradoras Mínimas Cormen páginas 445 até 458 e Deo páginas 39 até 44 e 55 até 57 e 61 até 64 13 Árvore Uma árvore é um grafo conexo existe caminho entre quaisquer dois de seus vértices e acíclico não possui ciclos Grafo acíclico mas não conexo é chamado de floresta Uma floresta também é definida como uma união disjunta de árvores árvore com 6 vértices e 5 arestas floresta 6 vértices e 3 arestas 14 Árvore Propriedades Em uma árvore existe um e apenas um caminho entre cada par de vértices Uma árvore com n vértices tem n1 arestas Uma floresta com n vértices e k componentes possui nk arestas Um grafo G é uma árvore se e somente se a remoção de qualquer aresta o desconectar grafo minimamente conectado Um grafo G com n vértices n1 arestas e nenhum ciclo é conexo 15 Árvore Geradora Árvore Espalhada ou Árvore de Extensão Uma árvore geradora de um grafo conexo G é um subgrafo de G que contém todos os vértices de G e é uma árvore Árvore geradora só é definida para grafos conexos porque toda árvore é conexa Grafos não conexos possuem florestas geradoras 16 Árvore Geradora Mínima Árvore Geradora Mínima é a árvore geradora de menor peso de G Dado um grafo G com pesos associados às arestas encontrar uma árvore geradora mínima de G 17 Árvore Geradora Mínima A partir de um grafo conectado não orientado GVE com uma função peso wER desejamos encontrar uma árvore geradora mínima correspondente a G Algoritmos Algoritmo de Prim Algoritmo de Kruskal Algoritmo de Prim o algoritmo de Prim é um algoritmo guloso empregado para encontrar uma árvore geradora mínima minimal spanning tree num grafo conectado valorado e não direcionado Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados A árvore geradora mínima corresponde a um heap mínimo httpsjoaoarthurbmgithubioedapostsheap 18 19 Algoritmo de Prim As arestas no conjunto A sempre formam uma árvore única A árvore começa a partir de um vértice de raiz arbitrária r e aumenta até a árvore alcançar todos os vértices em V Em cada etapa uma aresta que conecta um vértice de A a um vértice em VA é adicionada à árvore Quando o algoritmo termina as arestas em A formam uma árvore geradora mínima Durante a execução do algoritmo todos os vértices que não estão na árvore residem em uma fila de prioridade mínima Q baseada em um campo chave Para cada vértice v chavev é o peso mínimo de qualquer aresta que conecta v a um vértice na árvore πv é o pai de v na árvore 20 Algoritmo de Prim MSTPRIM Gwr for cada u VG do chaveu πu NIL chaver 0 Q VG while Q 0 do u EXTRACTMINQ for cada v Adju do if v Q e wuv chavev then πv u chavev wuv BUILDMINHEAP DECREASEKEY INSERE NA AGM Algoritmo de Prim Algoritmo de Prim Algoritmo de Prim Algoritmo de Prim 24 Algoritmo de Prim Análise de Complexidade BUILDMINHEAP é executado em tempo On O corpo do while é executado n vezes e como cada operação de EXTRACTMIN demora Olog n o tempo total para todas as chamadas a EXTRACTMIN é On log n O loop for é executado completamente Oe vezes pois a soma dos comprimentos de todas as listas de adjacências é 2e Dentro do loop for o teste de pertinência a Q pode ser implementado em tempo constante mantendose um bit para cada vértice que informa se ele está ou não em Q e atualizandose o bit quando o vértice é removido de Q A operação DECREASEKEY sobre o heap mínimo pode ser implementada em tempo Olog n Portanto o tempo total é On log n e log n Oe log n 25 Algoritmo de Kruskal Encontre uma aresta segura para adicionar à floresta crescente encontrando de todas as arestas que conectam duas árvores quaisquer na floresta uma aresta uv de peso mínimo Utiliza uma estrutura de dados de conjuntos disjuntos para manter vários conjuntos disjuntos de elementos Cada conjunto contém os vértices em uma árvore da floresta atual A operação FINDSETu retorna um elemento representativo do conjunto que contém u A combinação de árvores é realizada pelo procedimento UNION 26 Algoritmo de Kruskal MSTKRUSKALGw A for cada vértice v VG do MAKESETv ordenar as arestas de E por peso w não decrescente for cada aresta uvE em ordem de peso não decrescente do if FINDSETu FINDSETv then A A uv UNIONuv return A Algoritmo de Kruskal Algoritmo de Kruskal Algoritmo de Kruskal Algoritmo de Kruskal 31 Algoritmo de Kruskal Análise de Complexidade considerando que a implementação da floresta de conjuntos disjuntos seja feita com as heurísticas de união por ordenação e compressão de caminho Tempo para ordenar as arestas é Oe log e O segundo for executa Oe operações FINDSET e UNION sobre a floresta de conjuntos disjuntos que juntamente com as n operações MAKESET demoram ao todo o tempo Oneαn onde α é a função de crescimento muito lento Como G é supostamente conectado e n1 e assim as operações de conjuntos disjuntos demoram o tempo Oe αn Como αnOlog nOlog e o tempo total é Oe log e Considerando que e n2 log e Olog n e portanto podemos redefinir o tempo de execução do algoritmo de Kruskal como Oe log n 32 Algoritmos para o Menor Caminho Cormen páginas 470 até 475 33 Algoritmos para o Menor Caminho Um motorista deseja encontrar a rota mais curta possível do Rio de Janeiro a São Paulo Dado um mapa rodoviário do Brasil no qual a distância entre cada par de interseções adjacentes esteja marcada como podemos determinar essa rota mais curta 34 Algoritmos para o Menor Caminho Para resolver de forma eficiente problemas de menor caminho utilizamos um grafo ponderado GVE com função de peso wER que mapeia arestas para pesos de valores reais O peso do caminho pv0v1vk é o somatório dos pesos de suas arestas constituintes 35 Algoritmo de Dijkstra O algoritmo de Dijkstra resolve o problema de caminhos mais curtos de única origem em um grafo ponderado GVE para o caso no qual os pesos de arestas são não negativos Portanto para cada aresta 36 Algoritmo de Dijkstra Mantém um conjunto S de vértices cujos pesos finais de caminhos mais curtos desde a origem s já foram determinados O algoritmo seleciona repetidamente o vértice u VS com a estimativa mínima de caminhos mais curtos adiciona u a S e relaxa todas as arestas que saem de u A fila de prioridades mínima Q de vértices possui os valores d como chave 37 Algoritmo de Dijkstra DIJKSTRAGws for cada vértice v VG do dv πv NIL ds 0 S Q VG while Q do u EXTRACTMINQ S S u for cada vértice v Adju do if dv du wuv then dv du wuv πv u BUILDMINHEAP DECREASEKEY 38 Algoritmo de Dijkstra a b c d e a b c d e a b c d e a b c d e 39 Algoritmo de Dijkstra a b c d e a b c d e 40 Coloração Deo páginas 165 até 169 e 186 até 190 41 Coloração de Grafos Dado um grafo G como pintar seus vértices com várias cores de maneira que vértices adjacentes são pintados com cores diferentes Qual é o menor número de cores necessárias Dado um grafo G sem autoloops uma coloração de G é uma atribuição de cores aos vértices de G de maneira que cores diferentes são atribuídas a vértices adjacentes v1 v2 v3 v4 v5 42 Coloração de Grafos Se existe uma coloração para um grafo G que utiliza K cores então G é um grafo Kcolorido O número cromático de um grafo G denotado por XG é o menor número K para o qual G é Kcolorido XG 3 43 Coloração de Grafos Observações Não precisamos considerar grafos desconexos porque as cores utilizadas em um componente não tem efeito sobre as do outro componente Arestas paralelas não afetam a coloração Grafo não pode ter autoloops GRAFOS CONEXOS SIMPLES 44 Coloração de Circuitos Um grafo consistindo simplesmente de um circuito com n3 vértices é 2cromático se n é par e 3cromático se n é impar Um grafo simples G com pelo menos uma aresta é 2cromático se e somente se G não contiver circuitos de tamanho ímpar 45 Coloração de Grafos Se d é o maior grau dos vértices de um grafo simples G então XG d1 Se d é o maior grau dos vértices de um grafo simples G tal que G não contém um grafo circuito com um número ímpar de vértices e nem um grafo completo de d1 vértices então XG d 46 Exercício 11 Qual é o número cromático dos seguintes grafos a b 47 Coloração de Arestas Uma coloração de arestas de um grafo simples G é uma atribuição de cores às arestas de G de maneira que cores diferentes são atribuídas a arestas adjacentes Se existe uma coloração de arestas para um grafo G que utiliza K cores então G é um grafo Kcolorido de arestas O índice cromático de um grafo G denotado por XG é o menor número K para qual G é Kcolorido de arestas 48 Coloração de Arestas Três professores lecionam disciplinas em 4 períodos do curso Como alocar horários para as aulas sem que haja conflito para os professores e para as turmas João José Ana 1º Período 2º Período 3º Período 4º Período 49 Independência Dominância Casamento Deo páginas 169 até 173 e 177 até 182 50 Conjunto Independente Uma coloração de um grafo induz a um particionamento dos vértices em subconjuntos de vértices chamados conjunto independentes Conjunto independente conjunto de vértices do grafo no qual nenhum par de vértices do conjunto é adjacente 51 Conjunto Independente Conjunto independente máximo conjunto independente no qual nenhum vértice pode ser adicionado sem destruir a independência Número de independência número de vértices do maior conjunto independente máximo do grafo βG 52 Conjunto Dominante Conjunto dominante conjunto de vértices do grafo que dominam todos os vértices do grafo um vértice v pertence ao conjunto dominante ou é adjacente a um vértice que pertence 53 Conjunto Dominante Mínimo Conjunto dominante mínimo menor conjunto possível de vértices do grafo que dominam todos os vértices do grafo um vértice v pertence ao conjunto dominante ou é adjacente a um vértice que pertence 54 Casamento Uma agência de casamentos tem cadastrados r rapazes e m moças que desejam se casar A agência detectou a seguinte afinidade entre eles Como maximizar o número de casamentos R a p a z e s M o ç a s 55 Casamento Um casamento em um grafo é um conjunto de arestas no qual nenhum par de arestas do grafo é adjacente Casamento máximo é um casamento no qual nenhuma aresta pode ser incluída Casamento completo em grafos bipartidos é um casamento no qual todos os vértices de um dos conjuntos são casados a algum vértice do outro conjunto 56 Casamento Um casamento completo de V1 em V2 em um grafo bipartido G existe se e somente se todo subconjunto de r vértices de V1 for coletivamente adjacente a r ou mais vértices de V2 para todos os valores possíveis de r c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 57 Coberturas Deo páginas 182 até 186 58 Cobertura de Vértices Em um grafo G um conjunto g de vértices é chamado de cobertura de vértices se todas as arestas de G são incidentes a pelo menos um vértice de g Se este conjunto é o menor com tal propriedade dizemos que g é uma cobertura mínima de vértices 59 Cobertura de Arestas Em um grafo G um conjunto e de arestas é chamado de cobertura de aresta se todos os vértices de G são incidentes a pelo menos uma aresta de e Se este conjunto é o menor com tal propriedade dizemos que e é uma cobertura mínima de aresta