• Description

This course is an introduction to graph theory that includes topics related to network design and manipulation. We study the most commonly used graph families, graph operations, graph exploration algorithms, planar graphs, vertex coloration, optimization problems related to the concept of distance in graphs, as well as some fundamentals of  spectral graph theory. In addition, centrality measurements in graphs and centralization measurements are studied, including topological indices, the bipartivity measure of a network and reliability measures of weighted  networks. The contents studied can be applied to the analysis of complex networks including social networks, foodwebs, protein interaction networks, among others. Enrolled students will get a comprehensive introduction to recent works in this field.

• The subject within the syllabus as a whole

Graph theory and its Applications is an elective subject of 6 credits that offers to the students during the first semester. The content of the subject frames inside the discrete mathematics and is fundamental for the design, manipulation and analysis of networks. It recommends to the students do this subject before doing Complex Networks.

• Prior knowledge

Basic training in mathematics

• Learning objectives and results

The main goal of this course is to introduce students in the prolific research field of graph theory.

• Content

This course is an introduction to graph theory that includes topics related to network design and manipulation. We study the most commonly used graph families, graph operations, graph exploration algorithms, planar graphs, vertex coloration, optimization problems related to the concept of distance in graphs, as well as some fundamentals of  spectral graph theory. In addition, centrality measurements in graphs and centralization measurements are studied, including topological indices, the bipartivity measure of a network and reliability measures of weighted networks. The contents studied can be applied to the analysis of complex networks  including social networks, foodwebs, protein interaction networks, among others. 

• View the UOC learning resources used in the subject

• Guidelines on assessment at the UOC

The assessment process is based on students' own work and the assumption that this work is original and has been carried out by them.

In assessment activities, the following irregular behaviours, among others, may have serious academic and disciplinary consequences: someone else being involved in carrying out the student's assessment test or activity, or the work being not entirely original; copying another's work or committing plagiarism; attempting to cheat to obtain better academic results; collaborating in, covering up or encouraging copying; or using unauthorized material, software or devices during assessment.

If students are caught engaging in any of these irregular behaviours, they may receive a fail mark (D/0) for the assessable activities set out in the course plan (including the final tests) or in the final mark for the course. This could be because they have used unauthorized materials, software or devices (e.g. social networking sites or internet search engines) during the tests, because they have copied text fragments from an external source (internet, notes, books, articles, other student's projects or activities, etc.) without correctly citing the source, or because they have engaged in any other irregular conduct.

In accordance with the UOC's academic regulations , irregular conduct during assessment, besides leading to a failing mark for the course, may be grounds for disciplinary proceedings and, where appropriate, the corresponding punishment, as established in the UOC's coexistence regulations.

In its assessment process, the UOC reserves the right to:

• Ask the student to provide proof of their identity, as established in the university's academic regulations.
• Request that students provide evidence of the authorship of their work, throughout the assessment process, both in continuous and final assessment, by means of an oral test or by whatever other synchronous or asynchronous means the UOC specifies. These means will check students' knowledge and competencies to verify authorship of their work, and under no circumstances will they constitute a second assessment. If it is not possible to guarantee the student's authorship, they will receive a D grade in the case of continuous assessment or a Fail in the case of final assessment.

  For this purpose, the UOC may require that students use a microphone, webcam or other devices during the assessment process, in which case it will be the student's responsibility to check that such devices are working correctly.

• View the assessment model