Aula nš1
Dia: 24/2/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Apresentação do curso: Programa, Bibliografia e Avaliação.
Breve descrição das raízes históricas da Teoria Combinatórica
e do tipo de problemas que esta aborda.
Aula nš2
Dia: 27/2/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 0- Introdução:
Exemplos de problemas de existência, de contagem e enumeração
e de optimização em Teoria Combinatórica, incluindo alguns
problemas famosos e respectiva história.
Aula nš3
Dia: 3/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: I- Problemas de existência e contagem em Teoria Combinatórica
1. Problemas de existência:
O princípio dos pombais e algumas generalizações.
Exercícios e exemplos de aplicação.
Aula nš4
Dia: 6/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Não houve aula.
Aula nš5
Dia: 10/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 2. Princípios básicos de contagem:
Princípios da adição e da multiplicação.
3. Arranjos e combinações sem repetição.
Aula nš6
Dia: 13/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 4. Arranjos e combinações com repetição:
Estudo dos casos nos quais não se impõem restrições ao número de
vezes que cada elemento é repetido.
Aula nš7
Dia: 17/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Exemplos.
Estudo de alguns casos nos quais se impõem restrições ao número de
vezes que cada elemento é repetido. Exemplos.
Aula nš8
Dia: 20/3/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 5. Arranjos circulares.
6. Coeficientes binomiais e multinomiais. Teoremas binomial e
multinomial:
Triângulo de Pascal. Algumas identidades importantes envolvendo
os coeficientes binomiais.
Teorema binomial.
Aula nš9
Dia: 7/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Teorema multinomial.
7. Princípio de inclusão-exclusão:
Motivação e demonstração.
Aula nš10
Dia: 10/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Formulação alternativa para o princípio de inclusão-exclusão.
Exemplos de aplicação:
Determinação do número de combinações com repetição dos elementos
a_1, a_2, ... , a_n, r a r, nas quais, para cada i de 1 até n, o
i-ésimo elemento a_i aparece repetido quando muito r_i vezes.
Determinação do número de desencontros de comprimento n.
Soluções do "problema dos chapéus" e do "jogo dos pares".
Aula nš11
Dia: 14/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Determinação do número de funções sobrejectivas de um conjunto
com m elementos num conjunto com n elementos. Algumas aplicações.
8. Partições:
Motivação.
Aula nš12
Dia: 17/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Partições ordenadas e partições não-ordenadas.
Determinação do número de partições ordenadas de um conjunto com n
elementos em r subconjuntos, tais que o i-ésimo subconjunto possui
n_i elementos.
Determinação do número das correspondentes partições não-ordenadas.
Aula nš13
Dia: 21/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Determinação do número de partições ordenadas de um conjunto com n
elementos em r subconjuntos. Estudo do caso em que os subconjuntos
são não-vazios. Determinação do número das correspondentes partições
não-ordenadas. Números de Stirling de segunda espécie.
Determinação do número de partições não-ordenadas de um conjunto
com n elementos em r subconjuntos.
Aula nš14
Dia: 24/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Propriedades dos números de Stirling de segunda espécie. Construção
da respectiva tabela.
9. Relações de recorrência:
Motivação: o problema das coberturas perfeitas de um tabuleiro 2xn;
o problema de Fibonacci.
Aula nš15
Dia: 28/4/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Relação de recorrência de ordem k. Solução de uma relação de
recorrência.
Relações de recorrência lineares homogéneas com coeficientes
constantes. Exemplos. Uma abordagem directa (mas "ingénua"!).
Equação característica. Raízes características.
Aula nš16
Dia: 5/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Método geral de resolução das relações de recorrência lineares
homogéneas com coeficientes constantes. Exemplos.
Aula nš17
Dia: 8/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: II- Teoria dos Grafos
0. Introdução: breve nota histórica.
1. Noções básicas.
Grafos simples, grafos e grafos dirigidos.
Isomorfismo de grafos.
Aula nš18
Dia: 12/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Tolerância de ponto.
Aula nš19
Dia: 15/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Subgrafos. Subgrafos geradores.
União de grafos. Grafos conexos. Componentes conexas.
Grau de um vértice. Vértices isolados e terminais. Grafos completos.
Complementar de um grafo simples.
Aula nš20
Dia: 19/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Matrizes de adjacência e de incidência de um grafo. Algumas
propriedades.
Caminhos (abertos, fechados, sem repetição de arestas, sem
repetição de vértices, ciclos).
Grafos bipartidos. Grafos bipartidos completos. Algumas propriedades.
Aula nš21
Dia: 22/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 2. Grafos eulerianos:
Caminhos eulerianos. Teorema de Euler. Exemplos.
Aula nš22
Dia: 26/5/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: Nova leitura da demonstração do Teorema de Euler: outra
caracterização dos grafos eulerianos.
Grafos semi-eulerianos. Exemplos.
3. Grafos hamiltonianos:
Puzzle de Hamilton. Caminhos hamiltonianos. Grafos hamiltonianos.
Exemplos.
Complexidade deste problema relativamente ao de Euler. Algumas
condições suficientes para que um grafo seja hamiltoniano: Teorema
de Ore, Teorema de Dirac.
Aula nš23
Dia: 2/6/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 4. Alguns problemas importantes. O algoritmo de Dijkstra:
4.1. O problema do caminho mais curto.
4.2. O problema do carteiro chinês.
4.3. O problema do caixeiro-viajante.
Aula nš24
Dia: 5/6/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 5. Árvores:
Exemplos. Propriedades.
Aula nš25
Dia: 9/6/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: 6. Grafos planos e planares:
Problema das três casas.
Grafos imersos numa superfície. Grafos planares e grafos planos.
Representação plana de um grafo planar.
Exemplos.
Faces de um grafo plano. Fórmula de Euler. Aplicações:
- O famoso Teorema de Euler para poliedros convexos.
Aula nš26
Dia: 12/6/97
Hora: 14:00-15:30 (T1)
15:30-17:00 (T2)
Sumário: - Fórmula de Euler para grafos desconexos.
- Solução do problema das três casas: K3,3 não é planar.
- K5 não é planar.
Grafos homeomorfos. Teorema de Kuratowski. Contractibilidade de
grafos.