CI084 - Tópicos em Teoria do Grafos

Segundo semestre de 2005

SALA: PC07 na 4a. e Anf B na 6a. as 13:30hs

Notas de aula: (pdf)

Topicos:

Objetivos:

Apresentar aos alunos topicos avancados de teoria dos grafos.

Carga horária: 60 Créditos: 4 Responsável: Jair.

Bibliografia básica:

  1. Graph Theory, R. Diestel.
  2. Graph Theory with applications, A. Bondy e U.S.S.R. Murty.
  3. Algum livro de álgebra linear. Sugestões:
    1. Linear algebra, W. Greub.
    2. Elementary linear algebra, J. Munkres.
    3. Algebra linear, K. Hoffman, R. Kunze
    4. Espaços vetoriais de dimensão finita, P. Halmos

Documentos na web:

  1. Linear Algebra and applications to graphs I, L. Babai, REU'02
  2. Linear Algebra and applications to graphs II, L. Babai, REU'02
  3. Linear Algebra, L. Babai, REU'04
  4. Notes on Linear Algebra,Bruce Ikenaga
  5. Down with determinants, S. Axler
  6. An elementary proof of the Perron-Frobenius theorem for non-negative symmetric matricesK.Y. Lin.
  7. Notes on the perron-frobenius theory of nonnegative matrices - Mike Boyle
  8. Linear Algebra, Jim Hefferon
  9. Elements of Abstract and Linear Algebra, Edwin H. Connell
  10. Applied Linear Algebra and Matrix Analysis, Thomas S. Shores
  11. Elementary Linear Algebra Keith Matthews
  12. Spectral techniques in graph algorithms, N. Alon.
  13. Spectral techniques, semidefinite programs, and random graphs Amin Coja-Oghlan - Habilitationsschrift, Humboldt Universität zu Berlin.
  14. Expander Graphs and their Applications, N. Linial, A. Wigderson

Sistema de avaliação

Calendário de provas

Não haverá aulas em:

Listas de exercícios

Datas de entrega:
Listas:

Tópicos das aulas (em construção)
 
Aula 01 - O Teorema de Turan para K3 

Aula 02 - O Teorema de Turan para Kp 

Aula 03 - O Teorema de Turan para Kp. Teorema de Erdos-Stone. 

Aula 04 - Coloração de vértices. 

Aula 05 - no. de independencia e numero cromatico tipicos. 

Aula 06 - matrizes. 

Aula 07 - autovalores, autovetores, multiplicidades algebrica e geometrica de autovalores. 

Aula 08 - multiplicidades algebrica e geometrica de autovalores de matrizes diagonalizaveis. 

Aula 09 - matrizes simetricas. 

Aula 10 - teorema espectral real. 

Aula 11 - teorema de Courant-Fischer. 

Aula 12 - teorema de Courant-Fischer. 

Aula 13 - teorema do entrelacamento.

Aula 14 - teorema de Perron-Frobenius. 

Aula 15 - teorema de Perron-Frobenius.

Aula 16 - Introducao teoria espectral. 

Aula 17 - autovalores, grau dos vertices, conexidade. 

Aula 18 - grafos bipartidos, limitantes para no. cromatico. 

Aula 19 - distribuicao das arestas.

Aula 20 - grafos expansores. 

Aula 21 - autovalores tipicos. 

Aula 22 - numero típico de C4 rotulados. 

Aula 23 - numero tipico de arestas.

Aula 24 - Laplaciano. 

Aula 25 - Laplaciano. 

Aula 26 - Laplaciano. 

Aula 27 - Laplaciano. 

Jair Donadelli Junior
Last modified: Wed Aug 24 15:29:41 BRT 2005