CSI466 Graph Theory

Ementa

Introdução à teoria dos grafos. Conceitos básicos. Representação computacional. Percursos e Conectividade. Busca e ordenação topológica em grafos. Percursos abrangentes. Árvores geradoras. Problema do caminho mínimo. Problemas clássicos em grafos. Fluxo em Redes.
Ofertado em: [2013-2] [2013-2] [2014-1] [2014-1] [2014-2] [2014-2] [2018-1] [2019-1] [2019-2] [2019-2] [2020-1] [2020-1]

Conteúdo Programático
  1. Introdução: Definição de grafo, vértices e arestas. Processo de solução de problemas em grafos. Exemplos de aplicação. Problemas clássicos;
  2. Conceitos básicos em grafos: Ordem, incidência, adjacência, grau. Terminologia: grafo simples, regular, completo, complementar, subgrafos, grafos orientados. Isomorfismo;
  3. Representação de grafos: Densidade. Representação computacional de grafos por lista de adjacências e por matriz de adjacências;
  4. Percursos e conectividade: Passeio, caminho e ciclo. Grafos conexos e desconexos, componentes conexas, grafos f-conexos, sf-conexos. Árvores e florestas;
  5. Busca e ordenação topológica em grafos: Busca em largura, busca em profundidade, busca informada (heurística), ordenação topológica.
  6. Percursos abrangentes: Grafos eulerianos, teorema de Euler, grafos hamiltonianos. Noções de classes de problemas: P, NP e NP-Completo.
  7. Arvores geradoras: Subgrafo gerador, árvores geradoras, árvores geradoras mínimas. Algoritmo de Prim e de Kruskal.
  8. Problema do caminho mínimo: Definição. Algoritmos de Dijkstra, Belmann-Ford e Floyd-Warshal.
  9. Problemas clássicos em grafos: Coloração, conjuntos independentes e cliques, emparelhamentos, planaridade.
  10. Fluxo em Redes. Problema do fluxo máximo. Algoritmo de Ford-Fulkerson, Problema do Fluxo de Custo Mínimo, Algoritmo de Cancelamento de Ciclos Negativos. Modelagem de problemas reais como redes.
Bibliografia
  • Boaventura Netto, P. O. Grafos: Teoria, Modelos, Algoritmos. 5a edição. Edgar Blucher, 2012.
  • Jurkiewickz, S.; Boaventura Netto, P. O. Grafos: Uma Introdução prática. 1ª edição. Edgar Blucher, 2009.
  • Leisserson, C. E; Rivest, R. L.; Cormen, T. H.; Stein, C. Algoritmos: Teoria e Prática. 3a edição. Elsevier, 2012.

Offered: 

2020
2020-1 Plano de Ensino CSI466 - T21198 KB
2020-1 Plano de Ensino CSI466 - T22199 KB
A01 Apresentação da Discplina T21342 KB
A02 Introdução à Teoria dos Grafos292 KB
A03 Conceitos Básicos em Grafos805 KB
A04 Representação de Grafos601 KB
A05 Percursos e Conectividade375 KB
A06 Busca em Largura e em Profundidade752 KB
A07 Algoritmos em Grafos15.44 MB
A08 Ordenação Topológica466 KB
A09 Percursos Abrangentes614 KB
A10 Problema do Caminho Mínimo1.48 MB
A11 Árvores Geradoras798 KB
A12 Coloração640 KB
A13 Subconjuntos de Vértices245 KB
A14 Emparelhamentos434 KB
A15 Planaridade416 KB
A16 Fluxo em Redes485 KB