Optimization and Graphs Analysis

Recommended Prerequisites

NA

Teaching Methods

There are two types of classes: mainly expository classes, where theoretical concepts are introduced, together with motivating application examples; and classes where the students solve exercises and discuss problems under the guidance of the professor. The students are always encouraged to solve problems autonomously.
Formal lectures are complemented by tutorial time, offered to the students to support them with their personal work.

Learning Outcomes

The course is an introduction to the fundamentals of graph theory, network optimization and graph analytic tools. The study of basic notions on graph theory is followed by their application to classical network optimization problems and algorithms. The last part of the course focuses on tools to extract information about the structure and properties of graphs, which are useful for analyzing general graphs.
The students are exposed to different applications of graph concepts and problems, as well as to algorithmic thinking, while gradually preparing them for using tools to work with complex networks in the area of data science.
The course aims at developing the following skills: analysis and synthesis, organization and planning, clear oral and written communication, problem-solving skills. On the personal and systemic levels it also allows to develop self-learning skills and independent thinking.

Work Placement(s)

No

Syllabus

1. Introduction and applications
2. Fundamental concepts
2.1 Definition of graphs and extensions
2.2 Representations of graphs
2.3 Degrees and degrees sequences
2.4 Graphs isomorphism
2.5 Connectivity
2.6 Trees
2.7 Planar graphs
2.8 Colorations
3. Graph traversals
3.1 Eulerian circuits
3.2 Hamiltonian cycles
3.3 Graph traversals
4. Network optimization
4.1 Minimum spanning tree
4.2 Shortest path
4.3 Maximum flow – minimum cut
5. Graph analysis
5.1 Degrees distribution
5.2 Centrality measures
6. Communities
6.1 Clustering and Partitioning
6.2 Community Detection

Head Lecturer(s)

João Eduardo da Silveira Gouveia

Assessment Methods

Final Assessment
Exam: 100.0%

Assessment
Frequency: 100.0%

Bibliography

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.