Á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:
Teórica (por semana) |
Theory (weekly) |
Prática (por semana) |
Practice (weekly) |
Estudos (por semana) |
Study (weekly) |
Duração | Duration | Total | Total |
|---|---|---|---|---|---|---|---|---|---|
| 4 | 2 | 4 | 12 semanas | 12 weeks | 120 horas | 120 hours |
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