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]
- 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;
- Conceitos básicos em grafos: Ordem, incidência, adjacência, grau. Terminologia: grafo simples, regular, completo, complementar, subgrafos, grafos orientados. Isomorfismo;
- Representação de grafos: Densidade. Representação computacional de grafos por lista de adjacências e por matriz de adjacências;
- Percursos e conectividade: Passeio, caminho e ciclo. Grafos conexos e desconexos, componentes conexas, grafos f-conexos, sf-conexos. Árvores e florestas;
- Busca e ordenação topológica em grafos: Busca em largura, busca em profundidade, busca informada (heurística), ordenação topológica.
- Percursos abrangentes: Grafos eulerianos, teorema de Euler, grafos hamiltonianos. Noções de classes de problemas: P, NP e NP-Completo.
- Arvores geradoras: Subgrafo gerador, árvores geradoras, árvores geradoras mínimas. Algoritmo de Prim e de Kruskal.
- Problema do caminho mínimo: Definição. Algoritmos de Dijkstra, Belmann-Ford e Floyd-Warshal.
- Problemas clássicos em grafos: Coloração, conjuntos independentes e cliques, emparelhamentos, planaridade.
- 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.
- 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.