Área de Concentração: 45134

Concentration area: 45134

Criação: 18/02/2020

Creation: 18/02/2020

Ativação: 18/02/2020

Activation: 18/02/2020

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Docente Responsável:

Professor:

Yoshiko Wakabayashi

Objetivos:

Introduzir o estudante aos problemas e métodos e à linguagem da teoria dos grafos.

Justificativa:

Esta é uma disciplina básica para as áreas de Teoria da Computação, Combinatória e Otimização Combinatória.

Conteúdo:

Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos k-conexos. Grafos eulerianos. Árvores. Emparelhamentos em grafos bipartidos. Teorema de Menger. Grafos hamiltonianos. Conjuntos estáveis e cliques. Coloração de arestas. Coloração de vértices. Noções de planaridade.

Content:

[1] B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998. [2] J. A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008. [3] R. Diestel, Graph theory, 3a edição. Graduate Texts in Mathematics, 173. Springer-Verlag, Berlin, 2005. [4] P. Feofiloff, Exercícios de Teoria dos Grafos, 2009, http://www.ime.usp/~pf/grafos-exercicios/ [5] P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004, http://www.ime.usp/~pf/grafos-exercicios/ [6] R. Wilson, Introduction to Graph Theory, 4th ed., Prentice Hall, 1996.

Forma de Avaliação:

Bibliografia:

1. B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998. 2. J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008. 3. R. Diestel, Graph theory, 3a. edição. Graduate Texts in Mathematics, 173. Springer-Verlag, Berlin, 2005. 4. P. Feofiloff, Exercícios de Teoria dos Grafos, 2009, http://www.ime.usp.br/~pf/grafos-exercicios/ 5. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004, http://www.ime.usp.br/~pf/teoriadosgrafos/ 6. R. Wilson, Introduction to Graph Theory, 4th ed., Prentice Hall, 1996.

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial