Teoria dos Grafos - Elementos e Algoritmos

Prévia do material em texto

DISCIPLINA: Teoria dos Grafos (obrig.) 
CURSO: Bacharelado em Ciência da Computação / Bacharelado em Matemática 
PROFESSOR: Silvio Alexandre de Araujo ramal 2212 – DCCE – 
 e-mail: saraujo@ibilce.unesp.br (www.dcce.ibilce.unesp.br/~saraujo) 
 
PROGRAMA - 2006 
1. Elementos da Teoria dos Grafos 
 1.1. Formulação de problemas 
 1.2. Alguns tipos de grafos 
 - simples 
 - completos 
 - bipartidos 
2. Caminhos e Circuitos 
 2.1. Isomorfismo 
 2.2. Subgrafos 
 2.3. Grafos conexos 
2.4. Grafos Hamiltonianos e Eulerianos 
3. Grafos Planares 
 5.1. Teorema de Kuratowski 
4. Árvores 
 3.1. Propriedades 
 3.2. Árvores geradoras 
 3.3. Árvores binárias 
5. Conjunto de Cortes 
 5.1. Corte-vértice, corte fundamental 
 5.2. Cortes aresta, corte fundamental 
 5.3. Fluxo Máximo-Corte Mínimo 
6. Coloração, Cobertura e Partição 
 6.1. Coloração pelo vértice 
 6.2. Coloração pela aresta 
 6.3. Casamento e Cobertura 
7. Grafos Orientados 
 7.1. Conceitos básicos 
 7.2. Torneios 
8. Algoritmos 
8.1.Representação de grafos 
8.2.Algoritmos básicos 
 
 
BIBLIOGRAFIA 
1. Wilson, R. J. e Watkins, J. J. Graphs: na introductory approach 
2. Notas de aula (Socorro Rangel: http://www.dcce.ibilce.unesp.br/~socorro/tg2002) 
3. AHUJA, R.K., T. Magnanti e J.B. Orlin, Network Flows, Prentice Hall, 1993. 
4. Boaventura, P. O., Grafos : teoria, modelos, algoritmos, Edgard Blucher, ; 2001.. 
5. DEO, N.: Graph theory with applications to engineering and computer science, 
Prentice-hall, Inc. Englewood Cliffs, N.J., 1974. 
6. LUCCHESI, C.L.: Introdução à teoria dos grafos. IMPA, 1979. 
7. MCHUGH, J. A: Algorithmic graph theory, Englewood Cliffs, N.J. : Prentice Hall, 
1990. 
8. Reingold, E.M.: Combinatorial algorithms : theory and practice, Prentice-Hall, 
1977. 
9. TUCKER, A.: Applied combinatorics, erd. John Wiley & Sons, inc., N.J., 1995. 
10. SZWARCFITER, J.L. - Grafos e algoritmos computacionais, Ed. Campos, 1988. 
11. WILSON, R.J.: Introduction to graph theory, 3rd ed. The pitman Pressa Ltda, Bath, 
1985. 
CRITÉRIO DE AVALIAÇÃO 
A avaliação será feita em função do aproveitamento, duas provas escritas e um 
trabalho. Se necessário uma prova de recuperação. 
 
Curso de Ciências da Computação 
1ª prova: (peso1) (P1) : 03/10/2006 2ª prova: (peso 1) (P2) : 23/11/2006 
 
Curso de Matemática 
1ª prova: (peso1) (P1) : 06/10/2006 2ª prova: (peso 1) (P2) : 24/11/2006 
 
Prova de Recuperação: (PR): 05/12/2006 
 
Nota Final (NF) = (P1+ P2)/2 >= 5 Aprovado Se Nota Final<5 Recuperação 
Nota Recuperação = (NF + PR)/2 >= 5 Aprovado 
 
 
HORÁRIO DE ATENDIMENTO: 
Monitor Eduardo 
 
Terça sala 3C das 18:00hs às 19:00hs 
Quinta sala 2C das 18:00hs às 19:00hs