Introdução à Teoria dos Grafos

Objectivos

Pretende-se que os alunos tomem conhecimento de resultados fundamentais da Teoria dos Grafos e das respetivas aplicações, bem como de alguns algoritmos relacionados.

Caracterização geral

Código

10839

Créditos

6.0

Professor responsável

Maria Cecília Perdigão Dias da Silva

Horas

Semanais - 5

Totais - A disponibilizar brevemente

Idioma de ensino

Português

Pré-requisitos

A disponibilizar brevemente

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

A disponibilizar brevemente

Método de avaliação

Frequência

Será concedida Frequência a qualquer aluno que não falte injustificadamente a mais do que 2/3 das aulas lecionadas. Estão dispensados de frequência os alunos que a tenham obtido num no ano letivo 2018/2019 ou que tenham algum dos estatutos especiais previstos por lei.

A avaliação de conhecimentos é realizada através de Avaliação Contínua ou Exame de Recurso.

Avaliação Contínua

Ao longo do semestre serão realizados dois testes com duração de 1 hora 30 minutos e uma avaliação das aulas práticas (ap).  Cada teste tem classificação até um máximo de 20 valores e a avaliação das aulas práticas será entre 0 e 20 valores.

 1º Teste,  (t1): podem apresentar-se ao 1º teste todos os alunos inscritos na disciplina.

2º Teste, , (t2): podem apresentar-se ao 2º teste todos os alunos inscritos na disciplina que tenham obtido frequência ou tenham estatuto especial.

Avaliação das aulas práticas: o docente fornecerá no fim do semestre a classificação entre 0 e 20 valores. Esta corresponde à avaliação feita pelo docente, através do desempenho do aluno na resolução dos problemas propostos nas aulas.

A classificação da avaliação contínua (AC) é obtida através da seguinte fórmula:

AC= (0,45 t1)+(0,45 t2)+(0,1 ap)

O aluno é aprovado na disciplina se AC for superior ou igual a 9,5 valores. Se AC for inferior a 16,5 valores a nota final da disciplina será AC. Se AC for superior ou igual a 16,5valores o aluno pode optar entre obter uma nota final de 16 valores ou realizar uma prova suplementar de defesa de nota.

Exame de Recurso 

Podem apresentar-se a Exame de Recurso todos os alunos inscritos na disciplina que tenham obtido Frequência ou tenham estatuto especial. 

Na data e hora previstas para a realização do Exame de Recurso em junho de 2020, qualquer aluno inscrito na disciplina que tenha obtido Frequência ou tenha estatuto especial e que não tenha obtido aprovação na Avaliação Contínua pode realizar o exame de 3 horas. Se o aluno realizar o Exame de Recurso (a sua classificação é (er) e

AE=er

for superior, ou igual, a 9,5 valores, o aluno fica aprovado. Se AE for inferior a 16,5 a nota final da disciplina será AE. Se AE for superior ou igual a 16,5 valores o aluno pode optar entre obter uma nota final de 16 valores ou realizar uma prova suplementar de defesa de nota.

Melhoria de  nota

Os alunos têm direito a efetuar melhoria de nota, mediante inscrição nos prazos fixados, na época de recurso. Nesse caso, poderão efetuar o Exame de 3 horas

Logística

Só poderão efetuar qualquer das provas os alunos que, no ato da prova, sejam portadores de um documento oficial de identificação, onde conste uma fotografia (por exemplo, Cartão de Cidadão,  Bilhete de Identidade, Passaporte, algumas versões de Cartão de Estudante) e caderno de exame em branco.

Considerações finais

Em tudo o que o presente Regulamento seja omisso valem os Regulamentos Gerais da FCT-UNL.

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.

Cursos

Cursos onde a unidade curricular é leccionada: