MAC5770 - Introdução à Teoria dos Grafos

Pós-graduação/BCC. 1o. Semestre de 2008

Sinopse das aulas

• Março
  1. (Aula 1) 4/3/2008 Discussão inicial sobre a disciplina. Conceitos básicos: a linguagem da teoria dos conjuntos (Seções B.1 e B.2 do Apêndice B do [CLRS])

  2. (Aula 2) 6/3/2008 Continuação dos conceitos básicos. Indução matemática

  3. (Aula 3) 11/3/2008 Indução matemática

  4. (Aula 4) 13/3/2008 Conceitos básicos sobre grafos

  5. 18/3/2008 Semana Santa: Recesso escolar

  6. 20/3/2008 Semana Santa: Recesso escolar

  7. 25/3/2008 Não houve aula

  8. (Aula 5) 27/3/2008 Passeios, trilhas, e caminhos. Circuitos. Distância em grafos; diâmetro e cintura. Árvores e florestas

• Abril
  1. (Aula 6) 1/4/2008 Árvores e florestas

  2. (Aula 7) 3/4/2008 Árvore normais

  3. 8/3/2008 Professor no LATIN 2008: Não haverá aula ("break adiantado")

  4. 10/3/2008 Professor no LATIN 2008: Não haverá aula ("break adiantado")

  5. (Aula 8) 15/4/2008 Árvores normais (continuação)

  6. (Aula 9) 17/4/2008 Trilhas eulerianas. Grafos bipartidos

  7. (Aula 10) 22/4/2008 Emparelhamentos. Emparelhamentos em grafos bipartidos; coberturas de arestas por vértices. Teorema de König

  8. (Aula 11) 24/4/2008 Emparelhamentos em grafos bipartidos. Teorema de Hall, o enunciado e várias provas

  9. (Aula 12) 29/4/2008 Emparelhamento em grafos bipartidos regulares. Existência de 2-fatores em grafos 2k-regulares. Emparelhamento em grafos não necessariamente bipartidos. O Teorema de Tutte (enunciado)

• Maio
  1. 1/5/2008 Dia do Trabalho: Recesso escolar

  2. (Aula 13) 6/5/2008 Coloração de grafos. Coloração de vértices. Cotas superiores e inferiores elementares

  3. (Aula 14) 8/5/2008 Prova 1 [PDF | PS]

  4. (Aula 15) 13/5/2008 Caracterização e coloração de grafos k-degenerados. Teorema de Brooks (enunciado e início da demonstração)

  5. (Aula 16) 15/5/2008 Teorema de Brooks (término)

  6. (Aula 17) 20/5/2008 Coloração de arestas. Teorema de König. Teorema de Vizing (enunciado)

  7. 22/5/2008 Corpus Christi: Recesso escolar

  8. (Aula 18) 27/5/2008 Teorema de Vizing (demonstração)

  9. (Aula 19) 29/5/2008 ("Congresso da USP")

• Junho
  1. (Aula 20) 3/6/2008 Grafos hamiltonianos. Teoremas de Dirac e Chvátal

  2. (Aula 21) 5/6/2008 Pós-Prova 1

  3. (Aula 22) 10/6/2008 Grafos planares. Fórmula de Euler. Teorema de Kuratowski (enunciado)

  4. (Aula 23) 12/6/2008 Grafos planares (cont.). Teorema de Wagner (enunciado). Teorema das cinco cores

  5. (Aula 24) 17/6/2008 Pré-Prova 2

  6. (Aula 25) 19/6/2008 Prova 2

Calendário

         March 2008               April 2008     
    Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                       1            1  2  3  4  5 
     2  3  4  5  6  7  8      6  7  8  9 10 11 12 
     9 10 11 12 13 14 15     13 14 15 16 17 18 19 
    16 17 18 19 20 21 22     20 21 22 23 24 25 26 
    23 24 25 26 27 28 29     27 28 29 30 


          May 2008                June 2008         
    Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa   
                 1  2  3      1  2  3  4  5  6  7   
     4  5  6  7  8  9 10      8  9 10 11 12 13 14   
    11 12 13 14 15 16 17     15 16 17 18 19 20 21   
    18 19 20 21 22 23 24     22 23 24 25 26 27 28   
    25 26 27 28 29 30 31     29 30                  

Last modified: Wed Jun 18 13:21:28 BRT 2008