Otimização e Análise em Grafos

Conhecimentos de Base Recomendados

NA

Métodos de Ensino

As aulas são de dois tipos: aulas essencialmente expositórias, em que são introduzidos os conceitos teóricos e apresentados exemplos; e aulas de resolução de exercícios e de discussão de problemas pelos estudantes, sob a orientação do professor. Os estudantes são sempre encorajados a resolver os problemas de forma autónoma.
Os períodos de contacto em aula são complementadas por períodos de atendimento aos estudantes, para apoiar o seu trabalho independente.

Resultados de Aprendizagem

Esta unidade curricular é uma introdução aos fundamentos da teoria dos grafos, otimização de redes e ferramentas analíticas de grafos. O estudo das noções básicas sobre teoria dos grafos é seguido pela sua aplicação a problemas e algoritmos clássicos de otimização de redes. A última parte concentra-se em ferramentas para extrair informação sobre a estrutura e  propriedades de grafos.
Os alunos são expostos a diferentes aplicações de conceitos e problemas em grafos, bem como ao pensamento algorítmico, sendo gradualmente preparados para a utilização de ferramentas para interpretar e trabalhar com redes complexas na área de ciências de dados.
A unidade curricular visa desenvolver as seguintes competências instrumentais: análise e síntese, organização e planeamento, comunicação oral e escrita claras, competências de resolução de problemas. Em termos pessoais e sistémicos, também permite desenvolver capacidades de aprendizagem autónoma e pensamento independente.

Estágio(s)

Não

Programa

1. Introdução e aplicações
2. Conceitos fundamentais
2.1 Definição de grafo e extensões
2.2 Representações de grafos
2.3 Graus e sequências de graus
2.4 Isomorfismo de grafos
2.5 Conetividade
3.1 Circuitos eulerianos
3.2 Ciclos hamiltonianos
2.6 Árvores
2.7 Planaridade
2.8 Colorações
3. Travessia de grafos
3.3 Travessia de grafos
4. Otimização em redes
4.1 Árvore geradora mínima
4.2 Caminho mais curto
4.3 Fluxo máximo – corte mínimo
5. Análise de grafos
5.1 Distribuição de graus
5.2 Medidas de centralidade
6. Comunidades
6.1 Agrupamentos e partições
6.2 Deteção de comunidades

Docente(s) responsável(eis)

João Eduardo da Silveira Gouveia

Métodos de Avaliação

Avaliação
Frequência: 100.0%

Avaliação Final
Exame: 100.0%

Bibliografia

M. Van Steen. Graph theory and complex networks: An introduction,  Amsterdam: Maarten van Steen, 2010.
J. Simões Pereira, Matemática Discreta - Grafos, Redes, Aplicações, Editora Luz da Vida, 2009.
M. E. J. Newman, Networks 2nd edition, Oxford University Press, 2018.
M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, segunda edição, Wiley & Sons, 1990.