Introdução à Teoria dos Grafos
Código
10839
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Maria Cecília Perdigão Dias da Silva
Horas semanais
5
Total de horas
70
Língua de ensino
Português
Objectivos
Aspectos fundamentais da Teoria dos Grafos e Aplicações. Algoritmos.
Pré-requisitos
Conhecimentos de Matemática correspondentes às disciplinas de Álgebra linear I e II.
Conteúdo
1. Generalidades: Noção de grafo. Teorema do Aperto de Mãos. Isomorfismo. Sequências gráficas.
2. Conexidade.
3. Árvores e Arborescências: Algoritmos de Kruskal e de Prim.
4. Grafos Eulerianos: Algoritmo de Fleury.
5. Grafos Hamiltonianos.
6. Matrizes e Grafos.
7. Planaridade: Fórmula de Euler. Teorema de Kuratowski.
8. Coloração: Número cromático. Polinómio cromático.
9. Fluxos em redes: Teorema do Fluxo Máximo - Corte Mínimo. Algoritmo de Ford-Fulkenson.
10. Emparelhamentos e Recobrimentos: Teorema de Hall.
Bibliografia
1 – I. Cabral., Grafos e Aplicações, Texto Teórico e Exercícios, Departamento de Matemática, Universidade Nova de Lisboa, 1997,1998.
2 – C. Berge, Graphs, Second revised edition, North-Holland, London, 1985.
3 – R.J. Wilson, J.J. Watkins, Graphs: An Introductory Approach, John Wiley &Sons, New York, 1990
4 – J. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2004.
5 – N. Hartsfield, G. Ringel, Pearls in Graph Theory: A Comprehensive Introduction, revised and augmented, Academic Press, Boston, 1994.
Método de ensino
Aulas teórico-práticas participadas, com exposição oral de matéria e resolução de problemas.
Método de avaliação
Avaliação contínua: 3 testes de 75 minutos, sendo exigida uma classificação mínima de 6 valores no Teste 3.
Sendo Ti a nota do teste i, i=1,2,3, a nota final (ponderada) da avaliação contínua obtém-se pela fórmula AC = 0,3 T1 + 0,4 T2 + 0,3 T3 (se T3>=6).
Se AC >= 16,5 o aluno tem de efetuar uma prova extra.
Exame Final: se a nota do exame final for superior ou igual a 16,5 (valores), o aluno tem de efetuar uma prova extra.