Grafos e Algoritmos
Computacionais
Pontifícia Universidade Católica
1º semestre de 2009
Prof. Rainer Ronnie Pereira Couto
Programa








Introdução, conceitos básicos, classificação,
Isomorfismo.
Caminhos e circuitos, caminhamentos em grafos,
algoritmo de Dijkstra.
Grafos Eulerianos, grafos Hamiltonianos.
Árvores, árvore geradora mínima.
Cut-set e cut-vértices, grafos planares, espessura de
grafos, cruzamento de arestas, dualidade.
Coloração de grafos, dominância, independência,
cobertura.
Matching, fluxo em redes.
Problemas NP, problemas NP em grafos.
Bibliografia

Material disponibilizado pelo professor.
Livro: Graph Theory, Robin J. Wilson.

Bibliografia adicional.




Douglas B. West, Introduction to Graph Theory, Prentice-hall, 1996.
Nivio Ziviani, projeto de algoritmos, editora pioneira Thomson, 2005.
Reinhard Diestel, GraphTheory, Springer, 1997. (http://www.math.Unihamburg.De/home/diestel/books/graph.theory/GraphTheoryIII.pdf).
Avaliação


Página do curso:
 www.dcc.ufmg.br/~rainerpc/cursos/grafos
 e Learnloop
75% de presença em sala de aula


SEM abono de faltas
Distribuição dos pontos

2 provas de 25 pontos

3 trabalhos: 10 pts, 15 pts, 15 pts

2 Listas de exercícios: 5 pts cada
Alguns problemas que
serão abordados em
Grafos...
Problemas de grafos (1/11)

Três canibais e três missionários estão viajando juntos e
chegam à margem de um rio. Eles desejam atravessar
para a outra margem para, desta forma, continuar a
viagem. O único meio de transporte disponível é um barco
que comporta no máximo duas pessoas. Há uma outra
dificuldade: em nenhum momento o número de canibais
pode ser superior ao número de missionários pois desta
forma os missionários estariam em grande perigo de vida.
Como administrar a travessia?
Problemas de grafos (2/11)

Considere que temos três potes com capacidades de 8, 5 e
3 litros, respectivamente, os quais não possuem qualquer
marcação. O maior deles está completamente cheio
enquanto que os outros dois estão vazios. Estamos
interessados em dividir o vinho em duas porções iguais de
4 litros, tarefa esta que pode ser realizada por
transferências sucessivas de um vaso no outro. Qual o
menor número de transferências necessários para
completar a divisão?
Problemas de grafos (3/11)

A banda U2 tem um concerto que começa daqui a 17 minutos e
todos precisam cruzar a ponte para chegar lá. Todos os 4
participantes estão do mesmo lado da ponte. Você deve ajudálos a passar de um lado para o outro. É noite. Na ponte só pode
passar no máximo duas pessoas de cada vez. Só há uma
lanterna. Qualquer pessoa que passe, uma ou duas, deve passar
com a lanterna na mão. A lanterna deve ser levada de um lado
para o outro, e não pode ser jogada, etc. Cada membro da banda
tem um tempo diferente para passar de um lado para o outro. O
par deve andar junto no tempo do menos veloz:





Bono:- 1 minuto para passar
Edge:- 2 minutos para passar
Adam:- 5 minutos para passar
Larry:-10 minutos para passar
Por exemplo: se o Bono e o Larry passarem juntos, vai demorar 10
minutos para eles chegarem do outro lado. Se o Larry retornar com a
lanterna, 20 minutos terão passados e o show sofrerá um atraso.
Como organizar a travessia?
Problemas de grafos (4/11)

De forma a reduzir seus custos operacionais, 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.
Problemas de grafos (5/11)

No século 18 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 perguntavam-se se era possível cruzar as sete
pontes numa caminhada contínua sem que se passasse
duas vezes por qualquer uma delas.
Problemas de grafos (6/11)

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 seqüência que pudesse produzir tal
resultado. Você concorda com esta mãe?
Problemas de grafos (7/11)

Suponha que a área de venda de um caixeiro viajante
inclua várias cidades, muitas das quais, aos pares, estão
conectadas por rodovias. O trabalho do caixeiro requer que
ele visite cada cidade pessoalmente. Sob que condições
seria possível que ele estabelecer uma viagem circular
(que o leve ao ponto de partida) de forma a que ele visite
cada cidade exatamente uma vez?
Problemas de grafos (8/11)

Considere o jogo de xadrez. Seguindo as regras de
movimento do cavalo, é possível que um cavalo parta de
uma casa qualquer, percorra todo o tabuleiro visitando
cada casa uma e somente uma única vez e retorne à casa
inicial ?
Problemas de grafos (9/11)

A Empresa Brasileira de Correios e Telégrafos mantém
vários postos de coleta de correspondência espalhados
pela cidade, inclusive em bairros mais afastados. A
localização e a quantidade destes postos são por vezes
modificados de forma que diariamente o motorista
responsável por recolher a correspondência recebe um
esquema que mostra o melhor percurso para passar em
todos os postos de coleta. Este esquema é montado
manualmente por um funcionário da E.C.T.. Este
funcionário não agüenta mais as reclamações dos
motoristas de que as rotas que ele traça nunca são as
melhores e pede demissão. O chefe, sem saber como
tratar o problema, resolve contratar um especialista
(você), para resolvê-lo. Como você modelaria o problema?
Como encontrar a melhor rota? Que particularidades
devem ser tratadas?
Problemas de grafos (10)

Como o Orkut organiza sua base de dados? Como o Orkut
determina o caminho entre duas pessoas?
Rainer C > Carlos S > Leonardo D > Rodolfo B
Problemas de grafos (11)

Com quantas cores no máximo é possível colorir qualquer
mapa de forma que países vizinhos tenham cores
diferentes?
Dúvidas?