04_caminhamentos_em_grafos

Prévia do material em texto

Teoria dos Grafos 
 
 
Caminhamentos em grafos 
Tipos de caminhamentos em grafos 
1. Caminho 
2. Caminho fechado 
3. Trajeto 
4. Trajeto simples 
5. Circuito 
6. Circuito simples 
Caminhamentos em grafos 
Caminho (1/2) 
Caminhamentos em grafos 
Caminho (2/2) 
Caminhamentos em grafos 
Caminho fechado (1/2) 
Caminhamentos em grafos 
Caminho fechado (2/2) 
Caminhamentos em grafos 
Trajeto 
Caminhamentos em grafos 
Trajeto simples 
Caminhamentos em grafos 
Circuito 
Caminhamentos em grafos 
Circuito simples 
Terminologia de caminhamentos 
Caminhamentos em grafos 
Notação simplificada (1/2) 
Caminhamentos em grafos 
Notação simplificada (2/2) 
Identificando o caminhamento (1/3) 
Identificando o caminhamento (2/3) 
Identificando o caminhamento (3/3) 
Fecho transitivo direto 
Fecho transitivo inverso 
Contando caminhos de tamanho n (1/3) 
Contando caminhos de tamanho n (2/3) 
Contando caminhos de tamanho n (3/3) 
Referências 
• Slides do professor Antonio Alfredo Ferreira 
Loureiro, DCC/UFMG, Projeto e Análise de 
Algoritmos, 2010.