MCTA027-17 - Teoria dos Grafos Primeiro Quadrimestre de 2021


Avisos importantes

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

Objetivos

  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.

Ementa da disciplina

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.)

Aulas

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

Comunicação/Atendimento

Toda a nossa comunicação será centralizada no Discord.