- Informações gerais: bibliografia, critério de avaliação, etc.
- Uma visão geral sobre os tópicos que serão estudados
- Capítulo 1 - Conceitos e Resultados Básicos [cap 1] <=== nova versão (14/março)
- Lista 1 - entrega aos alunos
- Capítulo 1 - Conceitos e Resultados Básicos (cont.)
5/março (3a.f) - Feriado - Carnaval -- sem aula
- Capítulo 1 (cont.)
- (Alunos devem entregar parte da Lista 1 resolvida. Podem entregar a lista toda resolvida)
- Capítulo 2 - Grafos eulerianos [cap 2]
- (Alunos devem entregar o restante da Lista 1)
- Lista EXTRA 1 (Bônus 2 + Bônus 3) - disponibilizada no Paca
- Capítulo 2 - Grafos eulerianos (cont.)
- (Prazo para entrega do exercício Bônus 1 - opcional)
- (Lista 2 - disponibilizada no Paca)
- Capítulo 3 - Árvores [cap 3]
- Resumo e Slides de uma palestra feita na EACH (USP Leste) em 2007, por ocasião de um evento comemorativo dos 300 anos do nascimento de Leonhard Euler. Houve comemoração em várias universidades do mundo. [Olhem das páginas 1 a 58 e a pág. 75; o material das páginas 59 em diante serão abordadas futuramente no Capítulo 4 ou 5.] Não precisa levar este material na aula.
- An Historical Note: Euler's Königsberg Letters [artigo]
-
Material sobre grafos "randomly Eulerian from a vertex"
![[New!]](newave.gif)
<=====
- Capítulo 3 - Árvores (cont.)
- (Alunos devem entregar a Lista 2 resolvida)
- Lista 3 - enviada por email depois da aula
- (Cayley) Contagem de árvores rotuladas distintas com n vértices
- Capítulo 3 - Árvores (cont.)
- Árvore geradora de custo mínimo
- Árvore geradora de custo mínimo [artigo extra 1] [artigo extra 2] <=== notas históricas sobre MST
- Sobre o algoritmo de Prim (fazer a prova com ideia análoga à prova vista para o algoritmo de Kruskal)
- (Alunos devem entregar a Lista 3 resolvida)
- (Entrega da Lista 4 aos alunos -- em aula)
- Capítulo 4 - Grafos hamiltonianos [cap4.pdf]
- Capítulo 4 - Grafos hamiltonianos (cont.)
- (Teorema extra -- Chvátal & Erdös, 72 -- ideia da prova)
- (Lista 5 será disponiblizada no Paca)
- Material extra (relíquia de yw - trecho da dissertação
de mestrado "Sobre grafos hamiltonianos") - algumas condições suficientes para um grafo ser hamiltoniano) [Extra.pdf]
- Capítulo 5 - Emparelhamentos [cap5.pdf]
- Capítulo 5 - Emparelhamentos (cont.)
- (Entrega da Lista 6 aos alunos)
- Emparelhamentos e coberturas. Teorema (min-max) de Kőnig-Egerváry (para grafos bipartidos)
- Bio - Dénes Kőnig -- Jenő Egerváry
- (Alunos entregam a Lista 6)
- Capítulo 5 - Emparelhamentos (cont.)
- Recapitulação de todos os tópicos vistos e
exercícios.
- Aula de comentários sobre os exercícios das listas.
- Enunciado do Teorema de Tutte (caracterização de
grafos com emparelhamentos perfeitos).
- Primeira Prova
- Capítulo 6 - Coloração de arestas [cap6.pdf]
- (Alunos entregam a Lista 7 (antes da aula ou no Panda))
- Capítulo 6 - Coloração de arestas (cont.)
- (Entrega da Lista 8 aos alunos)
- Capítulo 7 - Coloração de vértices [cap7.pdf]
- Capítulo 7 - Coloração de vértices (cont).
- Teorema de Brooks (duas provas: árvore de Busca em
Profundidade, e cadeias de Kempe) [Brooks2.pdf]
Semana de break -- 20 a 24 de mai
AVISO 1 - Lista 9 pode ser entregue aaté 23h (dia 23/maio) <== Vejam
AVISO 2 - Podem entregar Bônus 9 até 28/maio (aula) <== Vejam
- Capítulo 8 - [cap8a.pdf]
Grafos planares - parte 1
- Capítulo 8 - Grafos planares (cont)
- Capítulo 8 - [cap8b.pdf] Grafos planares (cont) - parte 2
- Lista 10 (enviada por email) - a ser disponibilizada no Paca
- Capítulo 8 (cont) - revisão da prova do Teorema
de Kuratowski e coloração de grafos planares
- Aula de exercícios
- 2a. PROVA <=== CONFIRMADA!
- Capítulo 9 - Conexidade/Teorema de Menger - [
cap9.pdf] <=====
- Capítulo 9 - Conexidade/Teorema de Menger (cont.)