Marco C. Goldbarg

Programa

1- Introdução a Grafos e Algoritmos. Metodologia da disciplina, Calendário de atividades, trabalhos e            provas. Bibliografia. Notação Básica e Exemplos, Exercícios.

2 - Subgrafos e Grafos. Família de Grafos Especiais. Operações com Grafos e Estruturas Parciais.

     Exercícios.

3 - Estruturas de Dados para Grafos. Busca em Grafos. Exercícios.

4 - Exemplos de Aplicação dos Modelos em Grafos.

5 - Modelando Problemas Através de Grafos. Exemplos e Exercícios.

6 - Árvores geradoras – introdução.

7 - Árvores geradoras mínimas. Exemplos e Algoritmos. Exercícios.

8 - Variantes para árvores geradoras.

9 - Grafos especiais associados às árvores. Exercícios.

10 - Modelos de otimização aplicados às árvores. Exercícios.

11 – Conexidade – Algoritmos de Roy e Warshall.

12 - 1ª Prova

13 - Correção da 1ª prova. Dúvidas trabalhos. DATA PARA DEFINIÇÃO DO TEMA 1º TRABALHO

14 – Exercícios de Aplicação para modelagem de casos reais via grafos

15- Caminhos em grafos. Formulações e problemas reais associados.

16 - Caminhos mais curtos. Algoritmos de Dijkstra; Ford, More, Bellman; Floyd- Warshall

17 - Ciclos Eulerianos. Algoritmos de Hierholzer e de Fleury

18 - Exemplos de aplicação. Exercícios de caminhos em grafos

19- Modelos variantes para caminhos mais curtos. Caminhos mais curto com gargalo.

20 - Grafos e subgrafos especiais associados ao problema do caminho em grafos.

21 - Modelos de otimização aplicados aos caminhos mais curtos

22 - Coberturas em grafos. Exemplos e aplicações DATA PARA DEFINIÇÃO DO TEMA 2º TRABALHOS

23 – Algoritmos para cobertura de vértices e arestas.

24 - Atividade de Preparação dos Trabalhos

25 - Atividade de Preparação dos Trabalhos

​26 - Conjunto Dominante, Independente e K-Packing. Algoritmos e Exercícios

27 - Emparelhamento. Aplicações práticas. Conjunto estável. Aplicações práticas.

28 – Emparelhamento e Conjunto estável – Algoritmos de solução

​29 - Decomposição em subgrafos. Aplicações e algoritmos

​30 - Fluxo em redes. Conceitos. Caminhos de aumento de fluxo. Algoritmo de aumento de fluxo.

​31 - Aplicações reais de fluxo em redes

​32 - O problema da circulação, Algoritmos de fluxo máximo Dinitz

​33 - Algoritmos de fluxo de Ford e Fulkerson

​34 - recuperação

​35 - recuperação

​36 - 4ª Prova

 

Bibliografia

 

Fortemente recomendada:

[01] Goldbarg, M. C. & Goldbarg (2012), Grafos: conceitos, algoritmos e aplicações, Campus / Elsevier edt.

 

 

Complementar:

[01] Boaventura, P. O. N., (1996), Grafos: Teoria, Modelos e Algoritmos, Edgard Blücher, ltda.

[02] Brassard, G., e P. Bratley, (1988), Algorithmics: Theory & Pratice, Prentice-Hall, Inc, Englewood               Cliffs.

[03] Campello, R. E., e N. Maculan, (1994), Algoritmos e Heurísticas: Desenvolvimento e Avaliação de            Performance. Editora da Universidade Federal Fluminense, Niterói,  RJ.

[04] Goldbarg, M. C. e H. L. L. Pacca, (1999), Otimização Combinatória e Programação Linear: Modelos        e Algoritmos, Livro em disquete.

[05] Goldbarg, M. C. (1999), Teoria dos Grafos, Notas de aula.

[06] Hochbaum, D. S. (1997), Approximation Algoritms for NP-Hard Problems, PWS Publishing Company

[07]Papadimitriou, C. H., e K. Steiglitz, (1998), Combinatorial Optimization Algorithms and Complexity,           PrenticeHall, New York.

 

 

De apoio:

[01] Szwarcfiter, J. L. (1983), Grafos e Algoritmos Computacionais, Editora Campus.

[02] Terada R. (1982), Desenvolvimento de Algoritmos e Complexidade de Computação, Terceira Escola        de Computação, Rio de Janeiro, 1982.