Teoria dos Grafos

Terceiro quadrimestre de 2011
Horário: 3^a (14:00-16:00) e 5^a (14:00-16:00)
Sala de aula: 110-0 (bloco A)
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Novidades:

28/11 -- Lista 4 disponível
04/11 -- Conceitos após P1
19/10 -- Teste (prova hipotética, não vale nota) disponível
14/10 -- Lista 3 disponível
08/10 -- Lista 2 disponível
20/09 -- Datas das provas no site
20/09 -- Lista 1 disponível

Ementa

Introdução: Noções básicas; grafos orientados, não-orientados, bipartidos; grafos conexos e não conexos; Subgrafos e hipergrafos; Estruturas de dados para a representação de grafos. Caminhos e circuitos em grafos: Circuitos Eulerianos e Hamiltonianos; Caminhos de comprimento mínimo. Percursos em grafos: Em profundidade; Em largura. Árvores: Conceitos básicos; Árvores geradoras de grafos; Árvores geradoras mínimas. Exemplos de problemas: Coloração de vértices; Clique máximo; Conjunto independente de vértices; Caixeiro viajante; Problema do fluxo máximo em redes.

Avaliação

O conceito final da disciplina poderá ser:

F - Reprovado. O aluno deve cursar novamente a disciplina.
C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

A avaliação ser composta de duas provas, P₁ e P₂.

A avaliação final de cada aluno não será o resultado de alguma "conta" feita a partir dos valores das avaliações. O resultado de cada avaliação reflete o desempenho do aluno em todo o curso até aquele instante, e não é apenas uma "nota isolada". Isso significa que cada avaliação leva em conta também o resultado das avaliações anteriores. De maneira simples, cada avaliação mostra qual seria o conceito final do aluno se o curso terminasse naquele instante.

Não há "prova substitutiva", porque tal conceito não faz sentido no sistema de avaliação descrito acima.

Exercícios

Lista 1 (esta serve mais para perceber o espírito da disciplina): faça os exercícios do Capítulo 1 das notas de aula do prof. Jair.
Lista 2: faça os exercícios de 20 a 36; de 45 a 51; 54, 55, 71, 75, 76, 81.
Lista 3: faça os exercícios 90, 91, 92, 94, 100, 101, 102
Lista 4: faça os exercícios 108, 120, 121, 131, 135, 141, 145, 146, 154, 162, 181, 188, 190

Exemplo de prova: P₁ hipotética (o teste, que eu disse que não valeria nota e que daria na próxima aula).

Conceitos

RA	  após P1
-----------------
11003910	F
11151509	C
11020407	C
11013610	B
11034810	F
11028609	C
11017007	C
11029210	C
11137909	F
11012610	F
11007110	F
11107808	F
11011510	B
11064107	F
11043008	F

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Definições Iniciais
Subgrafos
Isomorfismo
Representações de grafos
Algoritmos para percursos e busca
Caminhos e circuitos
Conexidade
Árvores e Florestas
Emparelhamentos
Grafos dirigidos

Datas das avaliações:

P₁: 01/11
P₂: 06/12

Bibliografia

Principal

Usaremos as notas de aula do prof. Jair Donadelli, seguindo inclusive sua sequência de tópicos.

Secundária

Há também diversos livros úteis; a lista a seguir contém livros livres na internet e disponíveis na biblioteca da UFABC:

FEOFILOFF, P., KOHAYAKAWA, Y., WAKABAYASHI, Y. Teoria dos Grafos: uma introdução sucinta
CHARTRAND, Gary. Introductory graph theory. New York: Dover [511.5 / CHAi]
CHARTRAND, Gary; LESNIAK, Linda. Graphs & digraphs. 4th ed. Boca Raton: CRC Press [511.5 / CHAg4]
BOLLOBÁS, Béla. Modern graph theory. New York: Springer, c1998 [511.5 / BOLm]
BONDY, J. A; MURTY, U. S. R. Graph theory. New York: Springer, c2008 [511.5 / BONg]
CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L. and STEIN, C., Algoritmos - Teoria e Prática. Campus, 2002. [005.1 / CORi2] [005.1 / CORa]
DIESTEL, R. Graph Theory