Tópicos Especiais Engenharia de Computação e Informação (Cos013) - 2019/1


Engenharia de Computação e Informação


Esta é a página preliminar do curso de Teoria dos Grafos (Cos742). Não confundir com Teoria dos Grafos (Cos242), ministrada pelo Daniel Figueiredo.

O objetivo deste curso é apresentar uma abordagem mais teórica sobre Grafos. Neste curso pretentemos apresentar teoremas fundamentais em Teoria dos Grafos e estudar alguns problemas clássicos.

Peço que os alunos interessados enviem um e-mail para fbotler@cos.ufrj.br. Sugestões são bem vindas.

Professor: Fábio Botler



Ementa preliminar:

Teoremas de Hall e Tutte para emparelhamentos perfeitos; Teorema de König para emparelhamentos e coberturas em grafos bipartidos; Teorema de Brooks para coloração de vértices; Teorema das 5 cores, e Teorema das 4 cores; Teorema de Kuratowski para grafos planares. Teorema de Vizing para coloração de arestas; Decomposições; Teoria Extremal de Grafos.


Horário das aulas:

Início: 12/03/2019
3a. e 5a., 17-19h

Sala: H324-A

Monitoria:

Monitor: Luiz Hoffmann
Horário: quartas-feiras, 10h.
Sala: H-317-10-A


Listas

As listas deverão ser entregues até a data determinada, podem ser enviadas por email, porém é preferível que seja entregue, ainda que posteriormente, também a versão em papel. Sugerimos digitar a lista. Veja, por exemplo, o Overleaf.

Lista 1: Entregar até 11/04/2019
Lista 2: Entregar até 09/05/2019

Programação esperada:

Março
12 - 14Introdução, exemplos, definições básicas
19 - 21Emparelhamentos perfeitos e Teorema de Hall
26 - 28Teoremas de Hall, König, e Tutte
Abril
2 - 4Colorações de arestas
9 - 11Teorema de Vizing (assunto da P1 até aqui)
16 Coloração de vértices e Teorema de Brooks
18Feriadão
25 P1
Maio
30/04 - 2/05 Grafos Planares, Teorema das 5 Cores, Teorema das 4 Cores
7 - 9Teorema de Kuratowski
14 - 16 Decomposições de grafos
21 - 23 Teorema de Ramsey
28 - 30 Teorema de Turán e Teorema de Schur
Junho
Lagos
11Revisão
13P2

Bibliografia

Notas

FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y.
Teoria dos Grafos, uma introdução sucinta. São Paulo: IME-USP, 2011.

R. Morris; R. Imbuzeiro Oliveira.
Extremal and probabilistic combinatorics . XXVII Colóquio Brasileiro de Matemática (SBM/IMPA).

BONDY, J. A.; Murty, U. S. R.
Graph theory with applications. London: Macmillan, 1976.

DIESTEL, R.
Graph theory. Springer Publishing Company, Incorporated, 2018.

Links interessantes

Wikipedia: Mathematical proofs.