Teoria dos Grafos

Informações gerais

Ementa: Caminhos. Planaridade. Coloração. Grafos infinitos. Conectividade. Grafos orientados e não-orientados. Algoritmos em grafos. Problemas intratáveis.

Objetivos: Conhecer a Teoria dos Grafos através de uma visão introdutória dos seus principais aspectos teóricos, ressaltando a aplicabilidade para diversas áreas do conhecimento humano; e Conhecer algoritmos eficientes para a resolução de problemas clássicos na área.

Instituição: Universidade Estadual do Piauí (UESPI).
Período: 2019.3.
Dia/horário de aula: Seg a Sex - 8h às 11h20
Dia/horário para atendimento (sob demanda): Sáb - 8h às 11h
Ementa completa com conteúdo programático:

Slides

Nº Data Descrição Ref Arquivo
01 03/Fev Introdução e Apresentação da Discilina
02 03/Fev Conceitos Básicos - Parte 1
03 e 04 04/Fev Conceitos Básicos - Parte 1 (Exercícios)
05 e 06 05/Fev Conceitos Básicos - Parte 2
07 06/Fev Representação de Grafos
08 06/Fev Percursos em Grafos
09 07/Fev Correções de questões
10 07/Fev Primeira Avaliação - Assunto: Conteúdo Programático da Aula 01 até a Aula 09
11 e 12 10/Fev Conexidade
13 11/Fev Conexidade (continuação)
14 11/Fev Caminhamento em Grafos
15 12/Fev Medidas em Grafos
16 12/Fev Caminhos Mínimos
17 e 18 13/Fev Árvores e Árvores Geradoras Mínimas
19 14/Fev Correções de questões
20 14/Fev Segunda Avaliação - Assunto: Conteúdo Programático da Aula 01 até a Aula 19
21 17/Fev Correção da avaliação e Implementações
22 17/Fev Cortes em Árvores
23 18/Fev Conectividade
24 18/Fev Coloração
25 19/Fev Conjuntos Independentes
26 19/Fev Grafos Planares
27 e 28 20/Fev Apresentação de Trabalhos
29 20/Fev Apresentação de Trabalhos
30 21/Fev Terceira Avaliação - Assunto: Conteúdo Programático da Aula 01 até a Aula 29

Resultado Final

Segue a planilha com as médias finais. Em caso de dúvidas contactar-me por e-mail.
Repositório de Códigos
Segue o repositório com alguns códigos escritos em Python com algoritmos tratados em aula.

Atividade Final

Descrição da atividade final da disciplina de Teoria dos Grafos.

Materiais de Suporte

Livros, slides, artigos e apostilas

  1. Métodos de Prova. Antonio Alfredo Ferreira Loureiro (UFMG).
  2. Métodos de Prova - Por Indução. Antonio Alfredo Ferreira Loureiro (UFMG) e Olga Nikolaevna Goussevskaia
  3. Introdução à Teoria dos Grafos. Edson Prestes (2016).
  4. Grafos.Slides Vanessa Braganholo.

Ferramentas

  1. Creating Graphs in Python using Networkx. Ferramenta para criação de grafos em Python.
  2. Graph Online. Ferramenta para criação de grafos online.
  3. Documentação Networkx

Artigos web

  1. A Gentle Introduction to Graph theory.
  2. How to think in graphs: An illustrative introduction to Graph Theory and its applications.

Provas

Descrição Data Horário
AP1 07 de fevereiro 9h40 às 11h20
AP2 14 de fevereiro 9h40 às 11h20
AP3 21 de fevereiro 9h40 às 11h20

Referências

Básica:

1. BOAVENTURA NETO, P. O. Grafos: teoria, modelos e algoritmos. São Paulo: Edgard Blücher, 1996.
2. FURTADO, A. L. Teoria dos grafos: algoritmos. Rio de janeiro: LTC, 1973.
3. SZWARCFITER, J. L. Grafos e Algoritmos Computacionais. Rio de Janeiro: Campus.

Complementar:

4. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. 2.ed. Rio de Janeiro: Elsevier, 2002.
5. CAMPELLO, R. E.; MACULAN, N. Algoritmos e Heurísticas: desenvolvimento e avaliação de performance. Niterói: EDUFF, 1994.
6. LAFORE, R. Estruturas de dados e algoritmos em Java. São Paulo: Ciência Moderna, 2004.
7. LAUREANO, M. Estrutura de dados com algoritmos e C. Rio de Janeiro: Braspost, 2008.
8. PEREIRA, S. L. Estrutura de dados fundamentais: conceitos e aplicações. São Paulo: Érica, 2006.