MCTA027-17 - Teoria dos Grafos

Quadrimestre 1 de 2021


Avisos importantes

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.