Disciplina Introdução à Teoria de Grafos e Redes

A UC de Introdução à Teoria dos Grafos e Redes pretende dar ferramentas aos alunos para utilização de grafos em diversos problemas, partindo dos conceitos básicos, passando por problemas clássicos, e finalmente uma breve introdução de redes complexas, e as suas aplicações em problemas de Ciência de Dados.

CP1. Conceitos básicos (Definição, vértices, arestas, grafos orientados e não orientados, métricas, subgrafos, distância e conexidade, isomorfismos, invariantes e teoria espetral).

CP2. Redes e fluxos (Fluxo máximo, fluxo de custo mínimo)

CP3. Análise de redes (Representação de redes, visualização de redes, grau, medidas de distância e centralidade)

CP4. Grafos aleatórios (Erdös-Rényi, Watts-Strogatz, Barabasi-Albert)

CP5 Aplicações. em Data Science.

As aulas são divididas em aulas teóricas e práticas, sendo na sua maioria aulas expositivas presenciais. O aluno deverá dedicar 115h de trabalho assíncrono, e 52h em aulas presenciais.

ME1. Aulas expositivas.

ME2. Aulas práticas, com alguns momentos expositivos e outros com exercícios.

ME3. Listas de exercícios teóricas e práticas.

ME4. Desenvolvimento de projetos de maneira autónoma.

ME5. Recomendação de material complementar.

• L. Barabasi, M. Pósfai, Network Science, Cambridge University Press, 2016
• B. Bollobás, Random Graphs, Cambridge University Press, 2001
• D. M. Cardoso, J. Szymanski, M. Rostami, Matemática Discreta: combinatória, teoria dos grafos e algoritmos, Escolar Editora, 2008.
• P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004