Teoria dos Grafos

Curso ofertado na UFMG em 2021/2


Professor: Gabriel Coutinho


Descrição do curso

Ao final de cada aula, iremos sugerir os exercícios do livro do Diestel relacionados ao assunto da aula. Os exercícios marcados com sinais de ‘-‘ são “obrigatórios”. Os exercícios sem sinal são fortemente recomendados (faça pelo menos metade dos sugeridos). Os exercícios com sinais de + são mais difíceis, porém você deve tentar fazê-los também, principalmente se você está na pós.

Ao final do curso, se você precisar de pontos, será necessário mostrar todos os exercícios que você resolveu ao longo do semestre.


Aulas: terças e quintas, 9h25 as 11h05, no link do Teams postado no Moodle.

Playlist do youtube com aulas


Livro do Richard Diestel (principal material utilizado no curso)

Livro de Bondy e Murty

Algumas aulas básicas sobre grafos

Material produzido por professores da USP


Material suplementar para acompanhamento das aulas


Calendário de aulas e exercícios recomendados:

Outubro:

19. Introdução ao curso. Seções 1.1 a 1.3 do Diestel.
Exercícios (5a edição): 1 a 7, 11 e 12, e o 9 como desafio.

21. Seções 1.4 a 1.5 do Diestel.
Exercícios (5a edição): 20 a 23, 27 a 30.

26. Seções 1.6 a 1.7 do Diestel.

28. Seções 1.7 e 1.8 do Diestel.
Exercícios (5a edição): 36, 38, 40 a 43.

Novembro:

04. Seções 1.8 e 1.9 do Diestel.

09. Seção 1.9 do Diestel.

11. Friendship Theorem

16. Prova 1


18. Seção 2.1 do Diestel
Exercícios: 1 a 3, 5 e 6, 8 a 10

23. Seção 2.2 do Diestel
Exercícios: 12 a 14, 18 a 22

25. Notas de aula sobre Decomposição de Edmonds-Gallai
Exercício: 18 e 21 + Exercícios no final da seção 8 do pdf com notas de aula.

30. Seções 3.1 e 3.3 do Diestel
Três exercícios no final da seção 9 das notas de aula + Exercícios: 1-8, 15, 16, 21, 22.

Dezembro:

02. Seção 3.2 do Diestel (breve vista na seção 4.1 e começo de 4.2, e Proposição 4.2.6)
Exercícios: 9, 11 e 14. Três exercícios nas notas de aula (10.6, 10.8 e 10.9).

07. Seção 4.2 do Diestel
Exercícios: 3 a 9, e mais os três exercícios na seção 11 das notas de aula.

09. Seção 4.4 do Diestel
Exercícios: 16 a 23.

14. Seção 5.1 do Diestel + revisão
Exercícios 1 a 3 do Capítulo 5.

16. Prova 2


Janeiro:

4. Seção 5.2 do Diestel até Brooks.
Exercícios: 4 a 6, 8 e 9, 14 + exercícios nas notas de aula na seção 14.

6. Seção 5.3.
Exercícios: notas de aula da seção 15.

11. Fim da seção 5.2 e 5.5.
Exercícios: 16 a 18 + exercícios nas notas de aula na seção 16.

13. Seção 5.5.
Exercícios: 36 a 40, 43 e 45.

18. Seções 6.1 e 6.2

Exercícios 1 a 3.

20. Seções 6.3 e 6.5

Exercícios 5, 6, 10, 11, 19, 23.

25. Prova 3


Neste módulo, os tópicos não correspondem tão exatamente às Seções do Diestel. Siga principalmente pelas notas de aula.

27. Seção 7.1 do Diestel e começo da 10.1

Exercícios 1 a 4 do Capítulo 7 + exercícios da notas de aula da seção 20.

Fevereiro

1. Seções 9.1 e 9.2

Exercícios 1 a 4 do Capítulo 9 + exercícios da notas de aula da seção 21.

3. Seções 11.1 e 11.2

Exercícios 1 a 3 do Capítulo 11 + exercícios da notas de aula da seção 22

8. Seções 11.1 e 11.2

Exercício 7 do Capítulo 11 + exercícios da notas de aula da seção 23

10. Seções 11.1 e 11.2

Exercícios da notas de aula da seção 24