Introdução à Teoria dos Grafos

Caracterização geral

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. 

6 –  D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.

7 – M. Newman, Networks: An Introduction, Oxford University Press, 2010

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.

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 as classificações obtidas no 1º teste e  no 2º teste, respectivamente. Um aluno só poderá ficar aprovado na disciplina por avaliação contínua se

(0,5 t1)+(0,5 t2) ≥ 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.
2. Conexidade e caminho mais curto.
3. Árvores e Arborescências.
4. Grafos Eulerianos.
5. Grafos Hamiltonianos.
6. Matrizes e Grafos.
7. Grafos planares.
8. Coloração.
9. Fluxos em redes.
10. Emparelhamentos, coberturas, independentes.

11. Medidas de centralidade: centralidade de grau; centralidade de proximidade; centralidade de eficiência; centralidade de intermediação.

Cursos

Cursos onde a unidade curricular é leccionada: