Teoria dos Grafos - Parte 1 - Conceitos Basicos

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