• 🆕 28/01 - Página no ar.

1. Apresentar os conceitos e resultados básicos da Teoria dos Grafos;
2. Permitir o uso de grafos e suas propriedades para modelar problemas computacionais;
3. Apresentar algoritmos eficientes para problemas recorrentes em computação;
4. Tornar familiares certos padrões de soluções que ocorrem frequentemente em problemas envolvendo grafos.

Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multipartidos. Subgrafos. Isomorfismo. Conexidade. Florestas e árvores. Exemplos de problemas de interesse: coloração de vértices; clique máximo; caixeiro viajante; problemas de fluxo. Estruturas de dados para a representação de grafos. Percursos em grafos: em largura, em profundidade. Ordenação topológica. Árvores geradoras mínimas. Algoritmo de Kruskal. Caminhos mínimos em grafos: algoritmo de Dijkstra, algoritmo de Floyd-Warshall. Emparelhamentos: Teorema de Hall.

(Disponível na pg. 79 do projeto pedagógico.)

Videoaulas e materiais de apoio serão disponibilizados no Moodle da disciplina.