Faculdade de Ciências e Tecnologia

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.

Cursos