Introdução à Teoria dos Grafos

Caracterização geral

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

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, à distância, no Moodle 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: