CI084 - Tópicos em Teoria do Grafos

Primeiro semestre de 2007

sala: PC 07

4a e 6a 13:30

Tópicos:

Coloração, conjuntos independentes
Métodos de Álgebra Linear em Teoria dos Grafos
Grafos aleatórios
Grafos Expansores

Objetivos:

Apresentar aos alunos tópicos avançados em Teoria dos Grafos.

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

Bibliografia básica:

Notas de aula (se quiser uma copia, mande um email)
Graph Theory, R. Diestel.
Matrix Analysis, R. Horn e C. Johnson (Biblioteca)

Bibliografia complementar

Álgebra Linear, Mário Barone Jr (Biblioteca)
Linear Algebra, K. Hoffman, R. Kunze (Biblioteca)

Documentos na web:

Linear Algebra and applications to graphs I, L. Babai, REU'02
Linear Algebra and applications to graphs II, L. Babai, REU'02
Linear Algebra William Chen Lecture notes
Linear Algebra, L. Babai, REU'04
Down with determinants, (pdf) S. Axler
An elementary proof of the Perron-Frobenius theorem for non-negative symmetric matricesK.Y. Lin.
Notes on the perron-frobenius theory of nonnegative matrices - Mike Boyle
Linear Algebra, Jim Hefferon
Elements of Abstract and Linear Algebra, Edwin H. Connell
Elementary Linear Algebra Keith Matthews
Spectral techniques in graph algorithms, N. Alon.
Spectral techniques, semidefinite programs, and random graphs Amin Coja-Oghlan - Habilitationsschrift, Humboldt Universität zu Berlin.
Expander Graphs and their Applications, N. Linial, A. Wigderson

Sistema de avaliação

Provas e listas.
Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.

Calendário

26/02 - Início das aulas
06/04 - Feriado Sexta-feira santa
13/04 - Prazo final para cancelamento de matrícula
21/04 - Feriado Tiradentes
01/05 - Feriado Dia do trabalho
07/06 - Feriado Dia do trabalho
23/06 - Último dia letivo e encerramento da monitoria
04/07 - Prova final todo conteúdo

Tópicos das aulas

 
Aula 01 - apresentacao da disciplina. matrizes: notacao.

Aula 02 - matrizes: mais notacoes e definicoes (diag., similares, pol. caract, cof.).
          comb. linear, l.i., l.d.

Aula 03 - caracterizações de matrizes invertiveis. autovalores, autovetores.

Aula 04 - auto-espaco, multiplicidades algebrica e geometrica de autovalores.
 
Aula 05 - matrizes diagonalizaveis, autovetores e multiplicidades

Aula 06 - produto interno, ortogonalizacao

Aula 07 - teorema espectral real. 

Aula 08 - principio de Rayleigh

Aula 09 - teorema de Courant-Fischer  

Aula 10 - teorema do entrelacamento de Cauchy

Aula 11 - teorema de Perron-Frobenius para matrizes simetricas e  nao-negativas. 

Aula 12 - grafo, matriz de adjacencias, espectro, isomorfismo, passeio

Aula 13 - graus 

Aula 14 - subgrafos 

Aula 15 - caminhos, distancia e diametro

Aula 16 - componentes conexos, arvores

Aula 17 - conjuntos independentes e cliques

Aula 18 - numero cromatico

Aula 19 - prova

Aula 20 - laplaciano

Aula 21 - conexidade algebrica

Aula 22 - grafos expansores

Aula 23 - grafos expansores

Aula 24 - prova

Aula 25 - seminario I

Aula 26 - seminario II

Aula 27 - seminario III

Aula 28 - seminario IV

Aula 29 - seminario V

Jair Donadelli Junior

Last modified: Wed May 16 11:20:10 BRT 2007