grafos- UFMG

Projeto de Algoritmos – Cap.7 Algoritmos em Grafos

1

Motivação
• Muitas aplicações em computação necessitam considerar conjunto de conexões entre pares de objetos:
– Existe um caminho para ir de um objeto a outro seguindo as conexões?

Algoritmos em Grafos∗

– Qual é a menor distância entre um objeto e outro objeto?
– Quantos outros objetos podem ser alcançados a partir de um determinado objeto? • Existe um tipo abstrato chamado grafo que é usado para modelar tais situações.

Última alteração: 10 de Outubro de 2006

∗ Transparências elaboradas por Charles Ornelas, Leonardo Rocha, Leonardo
Mata e Nivio Ziviani

Projeto de Algoritmos – Cap.7 Algoritmos em Grafos

Aplicações
• Alguns exemplos de problemas práticos que podem ser resolvidos através de uma modelagem em grafos:
– Ajudar máquinas de busca a localizar informação relevante na Web.

2

Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1

Conceitos Básicos
• Grafo: conjunto de vértices e arestas.
• Vértice: objeto simples que pode ter nome e outros atributos.
• Aresta: conexão entre dois vértices.
3

– Descobrir os melhores casamentos entre posições disponíveis em empresas e pessoas que aplicaram para as posições de interesse.
– Descobrir qual é o roteiro mais curto para visitar as principais cidades de uma região turística. 0

aresta
1

4

2

vértice

• Notação: G = (V, A)
– G: grafo
– V: conjunto de vértices
– A: conjunto de arestas

3

Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1

4

Grafos Direcionados

Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1

5

Grafos Não Direcionados

• Um grafo direcionado G é um par (V, A), onde
V é um conjunto finito de vértices e A é uma relação binária em V .

• Um grafo não direcionado G é um par (V, A), onde o conjunto de arestas A é constituído de pares de vértices não ordenados.

– Uma aresta (u, v) sai do vértice u e entra
no