Diário

Aula 1: 5/3/2007, segunda

• Introdução
• Tarefa 1 (para quarta): Exr010 (parte), Exr019, E.1.60.

Aula 2: 7/3/2007, quarta

• Alguns tipos de digrafos  (simétricos, acíclicos, torneios, semicompletos, hamiltonianos, árvores divergentes, transitivos, bipartidos)
• Subdigrafos, caminhos em digrafos, árvores divergentes em digrafos
• Tarefa 2 (para 12/3): E.1.6, E.1.46, Exr014, E.2.35

Aula 3: 12/3/2007, segunda

• Digrafos acíclicos
• Digrafos fortes
• Decomposição em orelhas
• Digrafo das componentes fortes (§1.5)
• Tarefa 3 (para 14/3): Exr021, Exr020, E.7.2

Aula 4: 14/3/2007, quarta

• Indução/recursão mirim/adulta
• Digrafos transitivos
• Redução transitiva (§4.3)
• Fluxo em redes (§3)
• Teorema de Menger (T.7.3.1(a))
• Arco-conexidade
• Tarefa 4 (para 19/3): Exr022 (p.13), Exr023 (p.21)

Aula 5: 19/3/2007, segunda

• Caminhos internamente disjuntos
• Teorema de Menger (T.7.3.1(b))
• Digrafo bipartido D_ST
• Conexidade
• Aplicações de fluxos: emparelhamentos máximos em grafos bipartidos, subdigrafos geradores com graus especificados, cobertura disjunta por ciclos (§3.11), cobertura disjunta por caminhos e ciclos (§3.11)
• Tarefa 5 (para 21/3): E.7.5, E.3.54(a)

Aula 6: 21/3/2007, quarta

• Ciclos e caminhos hamiltonianos em digrafos semicompletos
• Teoremas de Rédei e Camion
• A propriedade da intercalação de caminhos
• Tarefa 6 (para 26/3): Exr027, E.1.26, E.4.25, Exr028

Aula 7: 26/3/2007, segunda

• Ciclos hamiltonianos em digrafos localmente semicompletos
• Tarefa 7 (para 28/3): E.5.13

Aula 8: 28/3/2007, quarta

• Caminhos hamitonianos em digrafos localmente semicompletos
• Ciclos hamiltonianos em digrafos com graus elevados (superficialmente)
• Ciclos hamiltonianos em digrafos multipartidos semicompletos (superficialmente)
• Tarefa 8 (para 9/4): E.3.68, E.1.54, E.1.53

Semana Santa: 2–7/4/2007

Aula 9: 9/4/2007, segunda

• Cobertura disjunta por caminhos (CDCa): Gallai-Milgram e Dilworth (§5.2 e §5.3)
• Subgrafo gerador forte mínimo (§6.11)
• Laminaridade e submodularidade
• Tarefa 9 (para 11/4): Exr040

Aula 10: 11/4/2007, quarta

• Prova de T.7.3.1.a (Menger)
• Árvores geradoras divergentes disjuntas (§9.5)
• T.9.5.1 (Edmonds)
• Dicortes e dijunções
• Toda dijunção é pelo menos tão grande quanto qualquer coleção disjunta de dicortes
• Tarefa 10 (para 16/4): Exr041, E.9.28, encontrar out-branchings disjuntos num digrafo manuscrito

Aula 11: 16/4/2007, segunda

• Teorema T.7.15.2 (Lucchesi-Younger)
• Tarefa 11 (para 18/4): exibir uma dijunção mínima e uma coleção disjunta máxima de dicortes no digrafo definido durante a aula

Aula 12: 18/4/2007, quarta

• T.7.15.2 (Lucchesi-Younger)
• Tarefa 12 (para 23/4): Exr048, Exr046, itens (49.f), (51) e (53) da prova do teorema T.7.15.2 (veja apêndice do Roteiro)

Aula 13: 23/4/2007, segunda

• Solução do exercício E.1.54.
• Laboratório: Exr033, Exr050, Exr044, Exr042, E.9.34.

Prova 1: 25/4/2007, quarta

Break (Dia do Trabalho): 30/4 – 4/5/2007

• Não teremos aulas.

Aula 14: 7/5/2007, segunda

• Aumento da arco-conexidade
• Lema L.7.6.2 (Frank)
• Tarefa 13 (para 9/5): Exr053 (veja solução)

Aula 15: 9/5/2007, quarta

• Lema L.7.6.2 (Frank)
• Splitting off e Teorema de Mader T.5.5.2 (§7.5)
• T.7.6.3 (Frank)
• Tarefa 14 (para 14/5): Exr039 (prova de P.7.1.1.b), Exr049, Exr065

Aula 16: 14/5/2007, segunda

• Aumento da conexidade (§7.7)
• T.7.7.3 (Frank-Jordán): sem a prova
• Tarefa 15 (para 16/5): Exr068

Aula 17: 16/5/2007, quarta

• Discussão do exercício Exr065 (aumento da arco-conexidade no caso k=1).
• Orientações fortes (§7.2)
• Orientações arco-k-fortes (§8.6)
• T.8.6.3 (Nash-Williams) (sem prova)
• Tarefa 16 (para 21/5): Exr072, E.1.57'

Aula 18: 21/5/2007, segunda

• Orientações e número cromático (§8.4)
• T.8.4.a (Gallai, Roy, Vitaver)
• Orientações com restrições de graus (§8.7)
• T.8.7.3 (Frank-Gyárfás)
• Tarefa 17 (para 28/5): Exr087, Exr078, Exr086 e E.8.41

Aula 19: 23/5/2007, quarta

• EXCEPCIONALMENTE, NÃO TEREMOS AULA. Precisamos pensar sobre a data conveniente para uma possível reposição.

Aula 20: 28/5/2007, segunda

• Orientações com restrições nos graus de conjuntos de vértices (§8.7)
• T.8.7.6 (Frank)
• Tarefa 18 (para 30/5): Exr105

Aula 21: 30/5/2007, quarta

• T.8.7.6 (Frank)
• Laboratório de exercícios: Exr118, Exr098, Exr119
• Mais exercícios: Exr100
• Tarefa 19 (para 11/6): Exr089, Exr099, Exr106

Break (Corpus Christi): 4–8/6/2007

Aula 22: 11/6/2007, segunda

• Fluxos submodulares (§8.8)
• Fluxos submodulares: condições necessárias
• T.8.8.1 (Edmonds-Giles)
• Tarefa 20 (para 13/6): Exr110

Aula 23: 13/6/2007, quarta

• T.8.8.1 (Edmonds-Giles)
• Existência de fluxos submodulares viáveis (§8.8.2)
• T.8.8.3, T.8.8.4, T.8.8.5 (Frank)
• Fluxo submodular de custo mínimo
• Aplicações: T.8.6.3 (Nash-Williams) e T.7.15.2 (Lucchesi-Younger)
• Tarefa 21 (para 18/6): Exr138, E.8.66
• Desafio opcional: Exr134(d)

Aula 24: 18/6/2007, segunda

• Fluxo inteiro nenhures-nulo (§8.5)
• Tarefa 22 (para 20/6): E.8.31

Aula 25: 20/6/2007, quarta

• Discussão do exercício E.8.66 (T.8.8.5 implica T.8.7.6)
• Teorema de Jaeger (8-fluxo nenhures nulo)
• Outros tópicos que eu gostaria de ter estudado:
  • Árvore geradora divergente de custo mínimo (§9.10)
  • Caminhos disjuntos ponto-a-ponto (§9.2-9.3)
  • Ciclos disjuntos e realimentação (§10.3-10.4)
  • Ciclos de comprimento k mod p (§10.6)

Prova 2: 25/6/2007, segunda

• Sala 256 bloco A