Institutional PortalUFPEL

Objetivo Geral:

Ensinar as técnicas básicas de contagem e noções sobre teoria de grafos.

1. Análise Combinatória
1.1. Um pouco da História
1.2. Princípio fundamental da Contagem
1.3. Arranjos
1.4. Permutações e Combinações
1.5. Aplicações
2. Binômio de Newton
2.1. Introdução
2.2. Teorema Binomial
2.3. Triângulo de Pascal
2.4. Expansão Multinomial
2.5. Polonômio de Leibniz
2.6. Uso de Pacote em Aplicações Computacionais.
3. Introdução a Teoria de Probabilidade
3.1. Introdução – Histórico
3.2. Espaço amostral e evento
3.3. Probabilidade de um evento
3.4. Adição de probabilidades
3.5. Multiplicação de probabilidades
3.6. Aplicações
4. Introdução a teoria dos grafos
4.1 Definição e Conceitos Preliminares
4.2. Representações de Grafos
4.3. Diferentes Tipos de Grafos
4.4. Grafos Dirigidos e Não dirigidos
4.5. Grafos Bipartidos
4.6. Multigrafo, Grafo Simples e Grafo Valorado
4.7. Grafos Isomorfos
4.8. Grafo Complementar
4.9. Grafo Parcial e SubGrafo
5. Caminhos
6. Tipo de Conexidade
7. Problemas de Caminhos
7.1. Menor Caminho de um vértice a qualquer outro vértice (Algoritmo de Dijkstra)
7.2. Menor Caminho Entre Dois Vértices (Algoritmo de Floyd)
7.3. Matriz de Roteamento
8. Grafos Eulerianos
8.1 Algoritmo de Fleury : (serve para traçar um ciclo eureliano)
9. Ciclos e Caminhos Hamiltonianos
9.1 Algoritmo: Ciclo Hamiltoniano de Custo Mínimo
9.2 Problema do Caixeiro Viajante.

Bibliografia Básica:

• Material Didático Produzido pelo LEMAD para essa disciplina (material impresso, vídeos, sites,...) HAZZAN, Samuel. Fundamentos de Matemática Elementar: combinatória, probabilidade. Volume 5. São Paulo: Atual, 1985.

Bibliografia Complementar:

• MORGADO, A. C. O. et alii. Análise combinatória e Probabilidade. Rio de Janeiro. IMPA, 1991. SANTOS, J. Plínio et alii. Introdução à Análise combinatória. Campinas, SP. Editora da UNICAMP, 1995. SCHEINERMAN, EDWARD. Matemática discreta: uma introdução. São Paulo: Pioneira Thomson Learning, 2003.