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 - 70

Idioma de ensino

Português

Pré-requisitos

Conhecimentos de Matemática da área da  Álgebra Linear, especialmente e matrizes e operações com matrizes.

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

Realização de avaliação à distância

Informamos que, ao realizar qualquer das provas à distância de ITG, cada aluno se compromete sob compromisso de honra a

  1.  Estar sempre ligado via Zoom apenas aos Professores, mantendo o microfone e vídeo do seu equipamento sempre ligados durante a prova.
  2. Não contactar NINGUÉM durante a realização das provas por qualquer meio, com eventual exceção de contacto com os Professores (apenas via Chat do Zoom) para algum esclarecimento pertinente sobre o enunciado.
  3. Realizar as provas SEM qualquer consulta de elementos disponíveis quer em papel, áudio, vídeo ou meio eletrónico.

Avaliação Contínua

Ao longo do semestre serão realizados dois testes, presenciais com duração de 1 hora 30 minutos e uma Avaliação das aulas. 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.

Podem apresentar-se a qualquer teste todos os alunos que à data do mesmo se encontrem inscritos na Unidade Curricular de Introdução à Teoria dos Grafos.

Avaliação das aulas: 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 no Moodle ou em TPC.

Sejam t1 e  t2  e aa as classificações obtidas no 1º teste, 2º teste e na Avalição das aulas, respectivamente. Um aluno só poderá ficar aprovado na disciplina por avaliação contínua se

(0,45 t1)+(0,45 t2)+(0,1 aa) ≥ 9,5

Neste caso a classificação final será dada por esta média arredondada às unidades, excepto se esta média for superior ou igual a 16,5, caso em que o aluno poderá optar entre ficar com a classificação final de 16 ou realizar uma prova complementar para defesa de nota.

 

Exame de Recurso 

Podem apresentar-se a Exame de Recurso todos os alunos inscritos na disciplina. 

Na data e hora previstas para a realização do Exame de Recurso, qualquer aluno inscrito na disciplina e que não tenha obtido aprovação na Avaliação Contínua pode realizar o exame de Recurso que terá a duração de 2h 30m. Se o aluno realizar o Exame de Recurso, a sua classificação é a obtida nesta prova. 

Se a classificação for superior, ou igual, a 9,5 e inferior, ou igual, a 16,4, o aluno fica aprovado com essa classificação, arredondada às unidades. Se a classificação for superior, ou igual, a 16,5 o aluno poderá optar entre ficar com a classificação final de 16 ou realizar uma prova complementar para defesa de nota.


Melhoria de  nota

Todo o aluno que pretenda apresentar-se a melhoria de nota deve inscrever-se, para esse efeito no CLIP (informações na Repartição Académica). A classificação do exame de melhoria é obtida de acordo com o indicado para o exame. Se este resultado for superior ao já obtido anteriormente na disciplina, será tomado como nota final. Caso contrário, não se verifica melhoria de nota.


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: