Introdução à Teoria dos Grafos
Objetivos
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
- Generalidades: Noção de grafo. Teorema do Aperto de Mãos. Isomorfismo. Sequências gráficas.
- Conexidade.
- Árvores e Arborescências: Algoritmos de Kruskal e de Prim.
- Grafos Eulerianos: Algoritmo de Fleury.
- Grafos Hamiltonianos.
- Matrizes e Grafos.
- Planaridade: Fórmula de Euler. Teorema de Kuratowski.
- Coloração: Número cromático. Polinómio cromático.
- Fluxos em redes: Teorema do Fluxo Máximo - Corte Mínimo. Algoritmo de Ford-Fulkenson.
- Emparelhamentos e Recobrimentos: Teorema de Hall.