I

Prévia do material em texto

SISTEMAS DE INFORMAÇÃO
ALGORITMOS 
EM 
GRAFOS
Profa. Michelle Nery Nascimento
PUC MINAS
Roteiro
¨ Objetivos da disciplina
¨ Ementa e Unidades de Ensino
¨ Motivação
¨ Bibliografia
¨ Avaliações
¨ Outros Procedimentos
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
2
Objetivos
3
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
¨ Capacitar o aluno a utilizar grafos como ferramenta para
modelagem e solução de problemas computacionais.
¨ Fornecer ao aluno condições para que ele desenvolva
soluções computacionais exatas e heurísticas para problemas
típicos envolvendo grafos.
¨ Levar o aluno a compreender problemas clássicos em grafos.
¨ Dar condições para que os alunos desenvolvam algoritmos
eficientes para a manipulação de grafos.
Ementa e unidades de ensino
4
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
¨ Grafos dirigidos e não-dirigidos. Estruturas de dados para representação de
grafos. Subgrafos. Isomorfismo
¨ Caminhos e circuitos, busca em profundidade e largura, algoritmos de caminho
mínimo. Ordenação Topológica
¨ Árvores, árvores geradoras mínimas, algoritmos de Prim e de Kruskal
¨ Conectividade em grafos dirigidos e não-dirigidos
¨ Planaridade, dualidade e algoritmos para detecção de planaridade
¨ Coloração de vértices, arestas e faces
¨ Particionamento: dominância, independência, cobertura e casamentos
¨ Fluxo em redes, algoritmos de fluxo máximo, cortes mínimos
¨ A teoria dos grafos é um assunto antigo com muitas
aplicações modernas.
¨ As ideias básicas de grafos foram introduzidas no
século XVIII, pelo famoso matemático suíço Euler: as
sete pontes de Königsberg
Introdução
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
5
Motivação
¨ Grafos: estrutura matemática
¨ Utilizados ao longo da história para proposição,
resolução, prova ou contra-prova de problemas
práticos variados
6
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – Pontes de Königsberg
¨ Uma cidade, um rio, 
quatro regiões, sete 
pontes.
¨ É possível sair de um 
ponto, passar por todas 
as pontes uma única vez 
e retornar ao ponto 
inicial?
7
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – Pontes de Königsberg
¨ Euler resolveu o 
problema em 1736
¨ Para isso, precisou de 
um modelo 
matemático...
8
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – Pontes de Königsberg
9
¨ ... E “iniciou-se” a 
teoria dos Grafos
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
¨ Curiosamente, se o número de pontes fosse apenas 
seis, como mostrado na figura, haveria uma solução 
bem simples
Motivação – Pontes de Königsberg
Motivação – Problema das 3 casas
11
¨ É possível conectar as
três casas aos três
serviços sem cruzar as
tubulações?
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – Problema das 3 casas
12
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – caminhos e rotas
13
¨ Se estou na PUC Contagem e preciso enviar livros por malote para 
todas as bibliotecas da RMBH, qual o melhor roteiro a seguir?
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
Motivação – conectividade
¨ Rede nacional de 
pesquisa – RNP
¨ Como otimizar 
conexões e 
capacidades para o 
tráfego existente?
14
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
¨ Rede de rotas de transporte
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
15
Motivação
¨ Rotas de distribuição de produtos ou serviços, como 
dutos de gás ou água
16
Motivação
¨ Estrutura química de uma molécula
17
Motivação
¨ Armazenamento de dados em “arquivos” - lista
indexada de nomes de pessoas
¨ Arquivo: Estrutura de árvore (um certo tipo de grafo)
¨ Qual o “caminho” mais breve para chegar a um dos
dados armazenados neste arquivo?
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
18
Motivação
PUC Minas – Sistemas de Informação – Algoritmos em Grafos
19
Uma transportadora deseja sair de 
A passando por todas
as cidades e retornando a A , de
maneira que o trajeto seja o mais
curto possível
Motivação
Bibliografia sugerida
¨ ASCENCIO, Ana Fernanda Gomes; Araújo, Graziela Santos
de. Estrutura de Dados: algoritmos, análise da
complexidade e implementações em Java e C/C++
¨ CORMEN, Thomas H. et al. Algoritmos: teoria e prática
¨ PEREIRA, J. M. S. Simões. Grafos e Redes - Teoria e Algoritmos
Básicos
¨ BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria,
modelos, algoritmos
20
PUC Minas – Sistemas de Informação – Algoritmos em Grafos