Baixe o app para aproveitar ainda mais
Prévia do material em texto
Teoria dos Grafos Conceitos Básicos Prof. Rômulo Alencar romulo.alencar@unifor.br Prof. Rômulo Alencar Teoria dos Grafos 2 Considerações Estes slides foram elaborados com base no material de professores anteriores da disciplina, especialmente os Profs. Maikol Rodrigues, Tibérius Bonates e André Coelho, e nos livros indicados na bibliografia da disciplina, com foco principal no livro “Algoritmos – Teoria e Prática” de Cormen et al. Prof. Rômulo Alencar romulo.alencar@unifor.br Prof. Rômulo Alencar Teoria dos Grafos 3 Conteúdo Conceitos Básicos Representação Computacional Busca em Grafos Ordenação Topológica Conexidade Fecho Transitivo Árvores Geradoras Mínimas Caminhos Mínimos Fluxo em Redes Prof. Rômulo Alencar Teoria dos Grafos 4 Introdução Por que estudar grafos? Abstraem de forma elegante os relacionamentos entre elementos de conjuntos discretos Importante ferramenta matemática com aplicação em diversas áreas do conhecimento Genética, química, telecomunicações, engenharia elétrica, computação, logística, dentre outros 4 Prof. Rômulo Alencar Teoria dos Grafos 5 Introdução O primeiro problema da Teoria dos Grafos foi formulado e resolvido pelo matemático Leonhard Euler, em 1736 No Rio Pengel, junto à cidade de Königsberg (hoje Kaliningrado), na então Prússia, existem ilhas, formando quatro regiões. Há um total de sete pontes as interligando. 5 É possível sair de uma das ilhas, passar uma única vez por cada uma das pontes e retornar ao ponto de origem ? Prof. Rômulo Alencar Teoria dos Grafos 6 Introdução As pontes de Königsberg Abstração de detalhes irrelevantes Área de cada ilha Formato de cada ilha Tipo da ponte, etc. 6 Prof. Rômulo Alencar Teoria dos Grafos 7 As pontes de Königsberg É possível cruzar as 7 pontes numa caminhada contínua sem que se que passasse duas vezes por qualquer uma delas? Euler transformou os caminhos em retas e suas interseções em pontos criando possivelmente o primeiro grafo da história. Prof. Rômulo Alencar Teoria dos Grafos 8 Introdução As pontes de Königsberg Não existe o trajeto desejado Euler provou que o trajeto só existe se e somente se concorrer um número par de pontes em cada região 8 Prof. Rômulo Alencar Teoria dos Grafos 9 Introdução As pontes de Königsberg Euler mostrou que não existe o trajeto proposto utilizando o modelo em grafos Verifique nos grafos abaixo se o trajeto proposto é possível Prof. Rômulo Alencar Teoria dos Grafos 10 Introdução Outros desenvolvimentos isolados que despertaram o interesse pela área Problema das 4 cores (De Morgan, 1850) Problema do ciclo Hamiltoniano (Hamilton, 1859) Teoria das árvores Circuitos elétricos (Kirchoff, 1847) Química orgânica (Cayley, 1857) 10 Prof. Rômulo Alencar Teoria dos Grafos 11 Introdução Problema das 4 cores Qual a quantidade mínima de cores para colorir um mapa de tal forma que países/estados fronteiriços possuam cores diferentes? 11 Prof. Rômulo Alencar Teoria dos Grafos 12 Introdução Problema das 4 cores É possível criar exemplos onde 3 cores são insuficientes De Morgan conjecturou em 1850 que 4 cores são suficientes Heawood mostrou em 1890 que 5 cores são suficientes Appel e Haken provaram a conjectura de De Morgan somente em 1976 12 Prof. Rômulo Alencar Teoria dos Grafos 13 Introdução Problema das 3 casas É possível conectar os 3 serviços às 3 casas sem haver cruzamento na tubulação? A teoria dos grafos mostra que não é possível 13 água luz telefone Prof. Rômulo Alencar Teoria dos Grafos 14 Introdução Problema do caminho mínimo 14 – Uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor caminho (o de menor distância) entre quaisquer duas cidades por ela servidas, de forma a que sejam minimizados os custos de transporte Prof. Rômulo Alencar Teoria dos Grafos 15 Introdução Problema do caixeiro viajante Um caixeiro viajante deseja visitar um dado grupo de cidades e retornar ao ponto de partida, percorrendo a menor distância possível 15 Prof. Rômulo Alencar Teoria dos Grafos 16 O Caixeiro Viajante Amplamente conhecido Fácil enunciado Classificado como NP-Difícil Grande aplicação prática Enorme relação com outros modelos Grande dificuldade de solução exata http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html Prof. Rômulo Alencar Teoria dos Grafos 17 Importância do PCV Com mais de 5 cidades, a solução anterior passa a ficar muito complicada... Por exemplo, com 20 cidades a quantidade de possíveis ciclos hamiltonianos é (19!)/2, o que dá aproximadamente 6 x 1016 Não se conhecem algoritmos eficientes para resolver esse problema Existem algoritmos heurísticos que dão soluções aproximadas Prof. Rômulo Alencar Teoria dos Grafos 18 Heurística: Vizinho mais Próximo 1 2 3 4 5 6 1 - 2 1 4 9 1 2 2 - 5 9 7 2 3 1 5 - 3 8 6 4 4 9 3 - 2 1 5 9 7 8 2 - 2 6 1 2 6 1 2 - Grafo Exemplo Prof. Rômulo Alencar Teoria dos Grafos 19 Heurística: Vizinho mais Próximo Prof. Rômulo Alencar Teoria dos Grafos 20 O problema do carteiro chinês Problema discutido pelo matemático chinês Mei-Ku Kuan Um carteiro deseja entregar suas cartas, percorrendo a menor distância possível e retornando ao ponto de partida Ele deve passar por cada estrada pelo menos uma vez, mas deve evitar passar por muitas estradas mais de uma vez. Prof. Rômulo Alencar Teoria dos Grafos 21 Introdução Modelagem com grafos Estamos interessandos nos objetos do problema e nas relações entre eles Quem são os objetos nos problemas apresentados? No problema da coloração: vértices são os estados, arestas são as divisas No problema das casas: vértices são as casas e os serviços, arestas são as tubulações No problema do caminho mais curto e do caixeiro viajante: vértices são as cidades, arestas são as vias de transporte 21 Prof. Rômulo Alencar Teoria dos Grafos 22 Exercício Um químico deseja embarcar os produtos A, B, C, D, E, F e G usando o menor número de containers. Alguns produtos não podem ser colocados num mesmo container porque reagem. Quaisquer dois produtos entre A, B, C e G reagem entre si. A reage com F e D. E também reage com F e D. Descreva o grafo que modela essa situação e use esse grafo para descobrir o menor número de containers necessários para embarcar os produtos com segurança. 22 Prof. Rômulo Alencar Teoria dos Grafos 23 Definição de Grafos Um grafo G = (V, E) é definido pelo par de conjuntos V e E, onde V : conjunto não vazio dos vértices ou nós do grafo E : conjunto de subconjuntos de V do tipo {u, v}, u e v ∈ V , que constituem as arestas do grafo Como a definição acima admite grafos com múltiplas arestas conectando dois vértices, são chamados também de multigrafos A ordem de um grafo G é dada pela cardinalidade (quantidade de elementos) |V| do conjunto de vértices 23 Prof. Rômulo Alencar Teoria dos Grafos 24 Definição de Grafos Seja, por exemplo, o grafo G = (V,E) dado por V = { v | v é uma pessoa} E = { {u,v} | u é amigo de v} O grafo pode ser determinado também pela enumeração dos elementos dos seus conjuntos V = { Maria, Pedro, Joana, Luiz} E = { {Maria,Pedro}, {Maria,Joana}, {Luiz,Pedro}, {Joana, Pedro} } 24 Prof. Rômulo Alencar Teoria dos Grafos 25 Grafo Não Dirigido No exemplo anterior, a relação de amizade é simétrica, isto é, considera-se que, se uma pessoa é amiga de outra, a recíproca é verdadeira Grafos com esta característica são ditos não dirigidos (não orientados) 25 Prof.Rômulo Alencar Teoria dos Grafos 26 Grafo Dirigido Considere agora o grafo definido por V = { v | v é pessoa da família Castro} E = { (u,v) | u é pai/mãe de v} Os conjuntos resultantes são V={Emerson, Isadora, Renata, Antônio, Cecília, Alfredo} E={(Isadora, Emerson), (Antônio, Renata), (Alfredo, Emerson), (Cecília, Antônio), (Alfredo, Antônio)} 26 Prof. Rômulo Alencar Teoria dos Grafos 27 Grafo Dirigido Obviamente, a relação expressa pelo grafo é assimétrica O grafo é dito dirigido (orientado, dígrafo), e as conexões entre os vértices, chamadas de arcos, são representadas por pares ordenados ao invés de conjuntos 27 Prof. Rômulo Alencar Teoria dos Grafos 28 Grafo Rotulado Um grafo G=(V,E) é rotulado em vértices (arestas) quando a cada vértice (aresta) estiver associado um rótulo 28 Prof. Rômulo Alencar Teoria dos Grafos 29 Grafo Ponderado Um grafo G=(V,E) é ponderado (ou valorado) quando existe uma ou mais funções relacionando V e/ou E a valores numéricos Para exemplificar, sejam V = {v | v é uma cidade com aeroporto} E = {(u,v,t) | há linha aérea ligando u a v, sendo t o tempo esperado de vôo} 29 Prof. Rômulo Alencar Teoria dos Grafos 30 Grafo Simples Um laço é uma aresta {v} ou um arco (v,v) que relaciona um vértice a ele próprio Um grafo sem laços e sem ligações redundantes é um grafo simples Como transformar o multigrafo abaixo em um grafo simples? 30 Prof. Rômulo Alencar Teoria dos Grafos 31 Subgrafo Um grafo Gs=(Vs, Es) é um subgrafo de G=(V,E) quando Vs ⊆ V e Es ⊆ E O figura abaixo ilustra a obtenção de subgrafos através da remoção de vértices e arestas 31
Compartilhar