Material das Aulas

Onde encontrar

O material da disciplina pode ser encontrado no Moodle ou no repósitório do GitHub.

Conteúdo

• Apresentação do curso
• Aula 01
  • Introdução;
  • Histórico;
  • Definição formal;
  • Exemplos;
  • Teorema do Aperto de Mãos;
  • Grafo Completo;
  • Grafo Regular;
  • Grafo Conexo e Desconexo;
  • Isomorfismo;
  • Grafo Complemento;
  • Grafo Bipartido;
  • Representação Computacional (Matriz e Lista de Adjacências).
• Aula 02
  • Isomorfismo;
  • Subgrafos;
  • Cadeia;
  • Caminho;
  • Ciclo;
  • Cintura e Circunferência.
• Aula 03
  • Resultados sobre caminhos;
  • Alcançabilidade;
  • Fecho Transitivo;
  • Fecho Transitivo Direito e Indireto;
  • Conexidade ou Conectividade.
• Aula 04
  • Busca em Grafos;
  • Busca Genérica;
  • Busca em Profundidade;
  • Busca em Largura.

• Aula 05
  • Caminhos mais curtos em grafos;
  • Algoritmo de Dijkstra.
• Aula 06
  • Algoritmo de Bellman-Ford.
• Aula 07
  • Algoritmo de Floyd-Warshall.
• Aula 08
  • Redes de Fluxo;
  • Fluxo Máximo;
  • Corte Mínimo.
• Aula 09
  • Algoritmo de Ford & Fulkerson.
• Aula 10
  • Máquinas de Turing;
  • Computabilidade;
  • Classe P;
  • Classe NP;
  • Classe NP-Completo;
  • P vs. NP.

• Aula 11
  • Casamento em grafos;
  • Casamento em grafos bipartidos;
  • O problema de atribuição;
  • O método Húngaro.

• Aula 12
  • Conjuntos Independentes;
  • Cliques;
  • Relação entre Conjuntos Independentes e Cliques;
  • Conjuntos Dominantes;
  • Relação entre Conjuntos Dominantes e Conjuntos Independentes.
• Aula 13
  • Coloração de Vértices;
  • Aplicações;
  • Número Cromático: Algumas Propriedades;
  • Coloração de Mapas;
  • O Teorema das 4 Cores;
  • Cadeias de Kempe.
• Aula 14
  • Árvores;
  • Árvores Geradoras;
  • O Problema da Árvore Geradora de Custo Mínimo;
  • O Algoritmo de Prim;
  • O Algoritmo de Kruskal;
  • O Algoritmo de Prim vs. O Algoritmo de Kruskal;
  • Aplicações.
• Aula 15
  • Ordenação Topológica;
  • Algoritmo Baseado em Busca em Profundidade;
  • Algorimo de Kahn;
  • Aplicações.
• Aula 16
  • Planaridade: introdução;
  • Grafos de Kuratowski;
  • Região ou Face;
  • Detecção de Planaridade;
  • Homeomorfismo;
  • O Teorema de Kuratowski.
• Aula 17
  • Caminhos e Ciclos Hamiltonianos;
  • Grafos Hamiltoniano e Semi-Hamiltoniano;
  • Caracterização de grafos Hamiltonianos.
  • Caminhos e Ciclos Eulerianos;
  • Grafos Euleriano e Semi-Euleriano;
  • Grafos Euleriano e Semi-Euleriano;
  • Caracterização de grafos Eulerianos.
• Aula 18
  
  • Problema do Caixeiro Viajante;
  • Casos Especiais;
  • Evolução dos Benchmarks;
  • Algoritmo de Christofides;
  • Aplicações Práticas.
• Aula 19
  • O Problema do Carteiro Chinês;
  • Complexidade;
  • Algoritmo de Hierholzer;
  • Algoritmo de Fleury.

 

Listas de Exercícios

• Lista de exercícios 1
• Lista de exercícios 2
• Lista de exercícios 3