Grafos e Algoritmos(TN718)

Informações

Código: TN718

Pré-requisito

Lógica para a Computação

Ementa

Teoria dos Grafos. Algoritmos de busca. Distância e caminhos mais curtos. Árvore geradora. Fluxo Máximo e Corte Mínimo.

Objetivos:

Ao final da disciplina o aluno deve:

(a) Dominar conceitos básicos em teoria dos grafos bem como saber justificar formalmente proposições e teoremas relacionados;

(b) Aplicar a teoria dos grafos para solucionar problemas de decisão e de otimização;

(c) Conhecer em profundidade e resolver os problemas básicos em grafos;

(d) Analisar a complexidade computacional dos algoritmos em grafos.

Conteúdo Programático

Sumário

1. Teoria dos Grafos
2. Algoritmos de busca
3. Distância e caminhos mais curtos
4. Árvore geradora
5. Fluxo Máximo e Corte Mínimo

Tópicos de Aula

01. Teoria dos Grafos

• Definições
• Propriedades básicas
• Representações
• Isomorfismo
• Grafos bipartidos
• Árvores
• Grafos eulerianos
• Grafos hamiltonianos
• Planaridade
• Grafos direcionados

02. Algoritmos de busca

• Busca em largura
• Busca em profundidade
• Árvores de busca
• Aplicações:
• Testar bipartição
• Testar DAG
• Encontrar componentes conexos
• Ordenação topológica

03. Distância e caminhos mais curtos

• Dijkstra
• Bellman*Ford
• Floyd-Warshall

04. Árvore geradora

• Kruskal
• Prim

05. Fluxo Máximo e Corte Mínimo

• Ford-Fulkerson
• Algoritmo de Edmonds*Karp
• Aplicações: Emparelhamento, Caminhos distintos

Referencia Bibliográfica

Bibliografia Básica

1. Bondy, A., Murty, M. R. Graph Theory. Springer-Verlag, 2008
2. Szwarcfiter, J. L., Teoria computacional de grafos: os algoritmos. Elsevier, 2018.
3. Kleinberg, J., Tardos, E. Algorithms Design. Addison-Wesley, 2005

Bibliografia Complementar

1. Dasgupta, S., Papadimitriou, C. H., Vazirani, U. Algorithms. Science Engineering & Math, 2007
2. West, D. W. Introduction to Graph Theory. Pearson, 2000
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introducit

Postado em 18/11/2013 - 08:19 - Atualizado em 15/08/2023 - 14:55