- 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] (a ser visto em várias aulas)
- Capítulo 1 - Conceitos e Resultados Básicos (cont.)
- Lista 1 - entrega aos alunos
- Capítulo 1 - Conceitos e Resultados Básicos (cont.)
- Capítulo 1 (cont.)
- (Alunos devem entregar parte da Lista 1)
- Capítulo 2 - Grafos eulerianos [cap 2] <==== versão nova (de 16/março/2020)
- ERRATA: No Corolário 2.3 corrigir no enunciado e no final da prova: trocar A(T) por A(G). [Queremos que as k trilhas contenham todas as arestas de G.]
- Lista 2 (tem exercícios sobre Capítulo 1 e Capítulo 2) - envio por email aos alunos
Material extra sobre Euler (para consultar em casa):
- 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.] Não precisa levar este material na aula.
- An Historical Note: Euler's Königsberg Letters [artigo]
- Material sobre Randomly Eulerian Graphs
- Capítulo 2 - Grafos eulerianos (cont.) - estudar
- Complementar os estudos com o material extra (Slides) do item anterior (ver solução feita por Euler para o Problema das 7 pontes de Königsberg)
- (Alunos devem entregar por email parte final da Lista 1)
- Capítulo 2 - Grafos eulerianos
- (Aula gravada -- a ser disponibilizada em breve no moodle USP (e-disciplinas))
- Se der, estudar as 3 primeiras páginas antes da aula
- Capítulo 3 - Árvores [cap 3]
- Capítulo 3 - Árvores (preferencialmente, ter o material impresso em mãos para acompanhar a aula)
- Capítulo 3 - Árvores (cont.) [cap 3-landscape]
![[New!]](newave.gif)
<=========== 1/abril
- Acompanhar com o material disponibilizado acima (o completado) - de 1/abril
- Lista 3 (veja no e-Disciplinas)
- (Fórmula de Cayley) Contagem de árvores rotuladas com n vértices.
- Árvores geradora de custo mínimo - Algoritmo de Kruskal
- Árvore geradora de custo mínimo [artigo extra 1] [artigo extra 2] <=== notas históricas sobre MST e referências a outros artigos (implementação)
- Algoritmo de Prim - provar que este algoritmo encontra uma árvore ótima (fazer a prova com ideia análoga à prova vista para o algoritmo de Kruskal) -- outra ideia: indução no número de vértices (contração da 1a. aresta selecionada). <===
- (Alunos fazem o teste em casa a partir das 9h30 para auto-avaliação -- discussão a partir das 10h00)
- Capítulo 4 - Grafos hamiltonianos [cap4.pdf] -- para acompanhar a aula online
- [Material (complementado durante a aula online)].
<===========
- 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 4 - Grafos hamiltonianos (cont.) - Material anterior e outros extras
- [Material (complementado
durante a aula online)].
<===========
- Capítulo 5 - Emparelhamentos - aula1 [cap5-parte1.pdf] - para acompanhar a aula online
- [Material (complementado durante a aula online)]. <===========
<===========
- Capítulo 5 (cont.) - aula2 - Emparelhamentos (material complementado na aula online - disponibilizado no Moodle).
- [Material (complementado durante a aula online)]. <===========
- Capítulo 5 (cont.) - aula3 - Emparelhamentos e coberturas.
- Emparelhamentos e coberturas. Teorema (min-max) de Kőnig-Egerváry (para grafos bipartidos).
- [Material das aulas 2 e 3 (complementado durante a aula online)]. <===========
- Bio - Dénes Kőnig -- Jenő Egerváry
- Enunciado do Teorema de Tutte (caracterização de grafos com emparelhamentos perfeitos).
- Tarefa para casa: ver o vídeo [Bill Tutte: A snapshot of His Life (palestra de Dan Younger, Waterloo)]
- Tarefa para casa: ler o texto William Tutte Memoir
- [Mais sobre Cobertura Mínima (como encontrar)]. <===========
- Capítulo 6 - Coloração de arestas [cap6-slides.pdf] - para acompanhar a aula online
- [Material da aula 1 do Cap.6 (complementado durante a aula online)]
- Capítulo 6 - Coloração de arestas (cont.)
- [Material todo do Cap.6 + Exercícios (complementado durante as aulas online)]
- Aula de exercícios (online)
- Capítulo 7 - Coloração de vértices [cap7-slides.pdf] -- para acompanhar a aula online.
- [Material da aula 1 (complementado durante a aula online)]
- Capítulo 7 - Coloração de vértices (cont).
- [Material das aulas 1 e 2 do Cap. 7 (complementado durante as aulas online)] <=======
- Aula gravada disponível no Google Drive.
- Capítulo 8 - Conexidade / Teorema de Menger -- [Cap8-slides.pdf] -- para acompanhar a aula online.
- [Material da aula 1 (complementado durante a aula online)]
- Capítulo 8 - Conexidade / Teorema de Menger (cont.)
- [Material das aulas 1 e 2 do Cap. 8 (complementado durante as aulas online)] <======
- Aula gravada disponível no Google Drive.
- Capítulo 9 - Grafos Planares [Cap9-aula1.pdf] -- para acompanhar a aula online.
- [Material da aula 1 do Cap. 9 (complementado durante a aula online)] <==========
- Capítulo 9 - Grafos Planares / Teorema de Kuratowski (aula2)[Cap9-aula2.pdf] -- para acompanhar a aula online.
-
[Material da aula 2 do Cap. 9 (complementado durante a aula online)] <===========
- Capítulo 9 - Grafos Planares (Cont.) - Coloração/Teorema das 4 cores.
- Explicação sobre o Trabalho Final (Monografia) que os alunos deverão entregar. <============= VEJAM!!! <--- AVISO IMPORTANTE