Aulas

• Aula 1 - 8 de agosto
  • Teste de conhecimentos prévios -- recapitulação de alguns conceitos e resultados básicos.
  • Preliminares (para fixar a notação e a terminologia) [ps][pdf]
• Aula 2 - 10 de agosto
  • Capítulo 1 - Emparelhamentos: Teorema de Berge, Teorema de Hall, Teorema de König, Teorema de Petersen.
• Aula 3 - 15 de agosto
  • Capítulo 1 - Emparelhamentos: Teorema de Tutte, algoritmo para encontrar emparelhamento máximo em grafos bipartidos (método húngaro).
• Aula 4 - 17 de agosto
  • Capítulo 1 - Emparelhamentos: algoritmo (dos botões) para encontrar emparelhamento máximo em grafos arbitrários.
  • Lista 1 de exercícios.
• Aula 5 - 22 de agosto
  • Capítulo 1 - Emparelhamentos: Teorema da decomposição de Gallai-Edmonds.
• Aula 6 - 24 de agosto
  • Capítulo 1 - Emparelhamentos:Teorema da decomposição de Gallai-Edmonds. Um algoritmo para encontrar um emparelhamento máximo baseado nesse teorema.
  • Provinha 1 (para casa).
• Aula 7 - 29 de agosto
  • Capítulo 2 - Conexidade: Teorema de Menger (várias versões).
• Aula 8 - 31 de agosto
  • Capítulo 2 - Conexidade - caracterização de grafos 2-conexos e 3-conexos.
• Semana da Pátria - 4 a 9 de setembro
• Aula 9 - 12 de setembro
  • Capítulo 2 - Conexidade
• Aula 10 - 14 de setembro
  • Capítulo 2 - Planaridade - resultados básicos
• Aula 11 - 19 de setembro
  • Capítulo 3 - Planaridade - Teorema de Kuratowski
• Aula 12 - 21 de setembro
  • Capítulo 3 - Planaridade. Espaço dos ciclos e dos cortes. Caracterização de MacLane/Whitney.
  • Provinha 2 (para casa).
• Aula 13 - 26 de setembro
  • Capítulo 3 - Planaridade/matróides dos circuitos, dos cortes, dualidade.
• Aula 14 - 28 de setembro
  • Capítulo 4 - Grafos perfeitos: introdução. grafos cordais, grafos de comparabilidade, grafos de intervalos, etc.
• Aula 15 - 3 de outubro
  • Capítulo 4 - Teorema dos grafos perfeitos (Lovász)
• Aula 16 - 5 de outubro
  • Capítulo 4 - Grafos perfeitos - poliedro dos conjuntos independentes.
• Semana de estudos - 10 a 14 de outubro
• Aula 17 - 17 de outubro
  • Capítulo 5 - Decomposição arbórea / largura arbórea (tree-width).
• Aula 18 - 19 de outubro
  • Capítulo 5 - Decomposição arbórea / largura arbórea (tree-width).
• Aula 19 - 24 de outubro
  • Capítulo 5 - Decomposição arbórea / largura arbórea (tree-width).
• Aula 20 - 26 de outubro
  • Capítulo 6 - Menores/conjuntos quase bem ordenados
• Aula 21 - 31 de outubro
  • Capítulo 6 - Menores - O Minor Theorem para árvores
• Aula 22 - 7 de novembro
  • Capítulo 6 - Menores - O Minor Theorem para grafos com largura arbórea limitada.
• Aula 23 - 9 de novembro
  • Capítulo 6 - Menores - uma idéia da prova do Minor Theorem para grafos arbitrários
• Aula 24 - Provinha 3 (para alguns alunos)