MO405 - Teoria dos Grafos

MC878A - Teoria e Aplicações de Grafos

Primeiro semestre de 2019

Prof. Orlando Lee




Conteúdo desta página



Avisos importantes

As notas dos testes e da prova estão aqui.

Horário das aulas e atendimento



Objetivos

O objetivo da disciplina é introduzir os conceitos básicos de Teoria dos Grafos e estudar vários problemas clássicos da área.



Pré-requisitos

O que é preciso saber para poder aproveitar bem a disciplina?

Possuir alguma familiaridade com algum formalismo matemático e com técnicas de demonstrações/provas de teoremas.

Eis um texto sobre notação de teoria de conjuntos escrito pelo Prof. Paulo Feofiloff.

Aqui segue um pequeno texto (longe de completo) sobre métodos de prova.

Outra técnica que usaremos extensivamente é o Princípio de Indução Matemática.



Material didático

Este semestre usarei o livro do Bondy e Murty [6] como guia. Aqui deixarei disponível as notas de aula que serão preparadas para as aulas. Cada nota corresponde a uma seção (ou duas) do livro e podem ser usadas em mais que uma aula. Tentarei colocar as notas com antecedência, mas não prometo.
  1. Section 1.1 Graphs and their representation
  2. Section 1.2 Isomorphisms and Automorphisms. Tentei explicar melhor os conceitos de automorfismo e grafos rotulados neste texto com um pouco mais detalhes do que está no livro.
  3. Section 1.3 Graphs Arising from Other Structures, Section 1.4 Constructing Graphs from Other Graphs e Section 1.5 Directed Graphs (modificado em 18/3)
  4. Section 2.1 Subgraphs and Supergraphs, Section 2.2 Spanning and Induced Subgraphs, Section 2.4 Decompositions and Coverings e Section 2.5 Edge Cuts and Bonds
  5. Section 3.1 Walks and Connection, Section 3.2 Cut Edges, Section 3.4 Euler Tours, Section 3.4 Connection in Digraphs
  6. Section 4.1 Forest and Trees, Section 4.2 Spanning Trees, Section 2.3 Modifying Graphs
  7. Section 5.1 Nonseparable Graphs, Section 5.2 Separations and Blocks, Section 5.3 Ear Decompositions
  8. Section 16.1 Maximum Matchings, Section 16.2 Matchings in Bipartite Graphs
  9. Section 9.1 Vertex Connectivity, Section 9.3 Edge Connectivity
  10. Section 18.1 Hamiltonian and Nonhamiltonian Graphs, Section 18.3 Path and Cycle Exchanges
  11. Section 14.1 Chromatic Number
  12. Section 17.1 Edge Chromatic Number


Listas de Exercícios

Durante o semestre serão disponibilizadas várias listas de exercícios. Para aprender a matéria você deve fazer muitos exercícios. Não será cobrada a entrega das listas. Cada aluno deve tentar resolver os exercícios individualmente e somente depois, em caso de dúvidas, procurar o docente ou outro colega.

Observação (18/3): eu reorganizei as listas. Agora os exercícios da Lista i se referem à nota de aula na(i).pdf



Ementa e critérios de avaliação

Essas informações estão aqui.



Datas importantes



Referências bibliográficas

Os livros recomendados são os de Bondy e Murty, do West (este tem um estilo parecido com o livro de BM e contém bastante exercícios) e do Diestel (este é mais avançado e cobre alguns tópicos mais recentes).

  1. Behzad, M. e Chartrand, G., Introduction to the Theory of Graphs, Allyn and Bacon, Boston, 1971.
  2. Balakrishnan, R. e Ranganathan, K., A Textbook of Graph Theory, Springer, 2012.
  3. Bollobás, B., Graph Theory: An Introductory Course, Graduate Texts in Mathematics 63, Springer-Verlag, New York, 1979.
  4. Bollobás, B. Modern Graph Theory, Graduate Text in Mathematics 184, Springer-Verlag, 1998.
  5. Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications, American Elsevier, New York, 1976.
  6. Bondy, J. A. and Murty, U. S. R., Graph Theory, Springer, 2008
  7. Diestel, R.; Graph Theory, Springer, 2005, terceira edi??o.
  8. Harary, F., Graph Theory, Addison-Wesley, Reading, Massachusetts, 1969.
  9. Lucchesi, C. L., Introdução à  Teoria dos Grafos, XII Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, 1979.
  10. Szwarcfiter, J. L., Grafos e Algoritmos Computacionais, Editora Campus Ltda., Rio de Janeiro, 2ª ed., 1986.
  11. West, D. B., Introduction to Graph Theory, Prentice Hall,1996.
  12. Wilson, R. J., Introduction to Graph Theory, 3rd ed., Longman Inc., New York, 1985.
  13. Wilson, R. J., Watkins, J. J., Graphs - An Introductory Approach, John Wiley & Sons, Inc., 1990.


Links