Logo UAB
2023/2024

Graphs, Topology and Discrete Geometry

Code: 104349 ECTS Credits: 6
Degree Type Year Semester
2503758 Data Engineering OB 1 2

Contact

Name:
Cesar Pablo Corcoles Briongos
Email:
cesar.corcoles@uab.cat

Teaching groups languages

You can check it through this link. To consult the language you will need to enter the CODE of the subject. Please note that this information is provisional until 30 November 2023.

Teachers

Sebastià Mijares Verdú
David Marín Pérez

Prerequisites

There are no prerequisites. However, students should be familiar with the most basic concepts of programming, fundamental algebra, such as set theory and applications. It is also recommended for students to have taken the courses “Fundamentals of Mathematics” and "Fundamentals of Programming".


Objectives and Contextualisation

 The course deals with topics included in the area of Discrete Mathematics focussing on the study of discrete objects. It begins with basic graph theory, path optimisation, algorithms in graphs and complexity of algorithms and problems. Following this, it contemplates basic concepts related to topology and discrete topology, as well as basic concepts on the geometry of curves and surfaces.

 


Competences

  • Develop critical thinking and reasoning and know how to communicate it effectively in both your own language and in English.
  • Make adequate representations of information both from a computational and a mathematical viewpoint.
  • Search, select and manage information and knowledge responsibly.
  • Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
  • Work cooperatively in complex and uncertain environments and with limited resources in a multidisciplinary context, assuming and respecting the role of the different members of the group.

Learning Outcomes

  1. Develop critical thinking and reasoning and know how to communicate it effectively in both your own language and in English.
  2. Identify and interpret the fundamental descriptors and properties of representations based on the geometry of the data.
  3. Identify and recognise the basic graph-traversing algorithms and demonstrate the capacity to optimise them.
  4. Interpret and apply the basic properties of directed and non-directed graphs.
  5. Search, select and manage information and knowledge responsibly.
  6. Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
  7. Work cooperatively in complex and uncertain environments and with limited resources in a multidisciplinary context, assuming and respecting the role of the different members of the group.

Content

Part I

  1. Previous concepts: sets, functions and complexity of algorithms

    1. Sets and operations with sets

    2. Cartesian product and binary relations

    3. Combinatorial elements

    4. Finite sets, infinite and numerable

    5. Complexity of algorithms and problems

    6. Functions of complexity. Polynomial and non-polynomial complexity

  1. Fundamentals of graphs

    1. Definitions. Variants of graphs

    2. Paths, circuits and distances

    3. Degrees and handshaking lemma

    4. Subgraphs and important types of graphs

    5. Graphic sequences (Havel-Hakimi)

    6. Graph representation

  1. Walk, trail, paths and optimal generating trees

    1. Exploration of graphs (DFS and BFS)

    2. Minimum cost paths (Dijkstra, Floyd)

    3. Characterization of trees

    4. Optimal generating trees (Kruskal)

  1. Planarity and colouring

    1. Basic results
    2. Characterization of planar graphs
    3. Colouring of planar graphs
  1. Eulerian and hamiltonian paths

  2. Algorithmic complexity

Part II

  1. Topology

    1. Topological space and basic properties

    2. Isomorphisms

    3. Simplexes, meshes and graphs as encoders of a discrete topology

  1. Geometry of curves and surfaces

    1. Parametric curves

    2. Parameter arc, implicit parametrization and level curves

    3. Basic descriptors of a curve in space: Frenet trihedron, torsion and curvature

  1. Surface geometry

    1. Parametric surfaces

    2. Tangent space

    3. First and second fundamental forms

    4. Diffeomorphisms

    5. Geodesic and minimal cost paths


Methodology

Theoretical course contents will be discussed in lectures. Regular, autonomous Personal Work will be expected from the students; lectures will not be based on reading available and required materials. These should be worked individually prior to sessions to maximize learning outcome.

During problem sessions, problems from a predefined list will be discussed, related to the course goals. Consistently with theory lectures, regular independent Personal Work will be required to maximize learning. In particular, individual solutions to a selection of problems will be expected prior to each session, and discussed in class.

Lab sessions will be held to assist the students in acquiring hands-on experience in topics related to the Syllabus. Microprojects will be completed by the students, who will be required to produce some deliverables.

Teaching will be predominantly in English.

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.


Activities

Title Hours ECTS Learning Outcomes
Type: Directed      
Labs 12 0.48 5, 1, 2, 3, 4, 6, 7
Problem sessions 12 0.48 5, 1, 2, 3, 4, 6
Theory lectures 26 1.04 5, 1, 2, 3, 4, 6
Type: Supervised      
Office hours 5 0.2 5, 1, 2, 3, 4, 6
Preparation of problems and lab submissions 12.5 0.5 5, 1, 2, 3, 4, 6, 7
Type: Autonomous      
Personal work 50 2 5, 1, 2, 3, 4, 6
Preparation for final exam 25 1 5, 1, 2, 3, 4, 6

Assessment

Continuous-assessment dates (and any change to them) will be published on the Campus Virtual.

Subject assessment (out of 10 points) will be carried out as follows:

Theory (6 points total):

Two individual partial tests, 6 points (3 points each). The first partial test will be given at the end of the first three chapters of the course; the second partial test will be given on finishing all the chapters of the course. These individual tests will consist mostly of exercises in the style of those worked on during the course; a smaller part will consist of more theoretical questions.

Final exam, 6 points. Those who have not passed the subject through the individual partial tests will have the option to take a single final exam as a re-assessment grade to compensate for both individual partial tests.

Problems (1.5 points):

As part of continuous assessment, activities must be carried out or exercises must be solved by applying the given algorithms (via online quizzes, for example). The non-online activities or exercises will take place during the exercise sessions.

Labs (2.5 points):

As part of continuous assessment, certain deliverables must be submitted, which will be anounced with appropriate anticipation. The final score of this part will be calculated as the average score of these submissions.

An overall grade of 5 or higher is required to pass the subject. A "non-assessable" grade cannot be assigned to students who have participated in any of the individual partial tests or the final exam. No special treatment will be given to students who have completed the course in previous academic years, except that the lab lab/seminar previously obtained can be assigned to this course gradebook. In order to pass the course with honours, the final grade must be a 9.0 or higher. Because the number of students with this distinction cannot exceed 5% of the number of students enrolled in the course, this distinction will be awarded to whoever has the highest final grade. In case of a tie, partial-test results will be taken into consideration.

It is important to bear in mind that no assessment activities will be permitted for any student at a different date or time to that established, unless for justified causes duly advised before the activity and with the lecturer’s previous consent. In all other cases, if an activity has not been carried out, this cannot be re-assessed.

In the case of exercise resolution, a review may be requested after the date of the activity or the date of closure of the quiz. For all other assessment activities, a place, date and time of review will be indicated allowing students to review the activity with the lecturer. In this context, students may discuss the activity grade awarded by the lecturers responsible for the subject. If students do not take part in this review, no further opportunity will be made available.

Single assessment

If you want to follow the single assessment model, you will take a synthesis test (counting for 50% of the assessment) and you will be provided with exercises (similar to those seen in the problems classes, for 35% of the assessment) and lab work (similar to those seen in the continuous assessment, for the final 25%) that can be handed in until the day of the synthesis test, for evaluation along with it.

Plagiarism and other academic irregularities

Notwithstanding other disciplinary measures deemed appropriate, and in accordance with the academic regulations in force, assessment activities will receive a zero whenever a student commits academic irregularities that may alter such assessment. Assessment activities graded in this way and by this procedure will not be re-assessable. If passing the assessment activity or activities in question is required to pass the subject, the awarding of a zero for disciplinary measures will also entail a direct fail for the subject,with no opportunity to re-assess this in the same academic year. Irregularities contemplated in this procedure include, among others: the total or partial copying of a practical exercise, report, or any other evaluation activity; allowing others to copy; presenting group work that has not been done entirely by the members of the group; presenting any materials prepared by a third party as one’s own work, even if these materials are translations or adaptations, including work that is not original or exclusively that of the student; having communication devices (such as mobile phones, smart watches, etc.) accessible during theoretical-practical assessment tests (individual exams).

To consult the academic regulations approved by the Governing Council of the UAB, please follow this link: http://webs2002.uab.es/afers_academics/info_ac/0041.htm


Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Submission of lab deliveries 25% 3 0.12 5, 1, 2, 3, 4, 6, 7
Tests based on exercises from the problems class 15% 1.5 0.06 5, 1, 2, 3, 4
Two partial exams 60% 3 0.12 5, 2, 3, 4, 6

Bibliography

  • J.M. Basart. Grafs: fonaments i algorismes. Manuals de la UAB, 13. Servei de publicacions de la UAB, 1994.
  • C. Berge. Graphs. North-Holland, 1991.
  • N.L. Biggs. Matemàtica discreta. Vicens-Vives, 1994.
  • N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.
  • J. Gimbert, R. Moreno, J.M. Ribó, M. Valls. Apropament a la teoria de grafs i als seus algorismes. Eines 23, edicions de la UdL, 1998.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • M. P. do Carmo. Geometría diferencial de curvas y superficies. Alianza Editorial, 1995.
  • J. R. Munkres, Topología, Prentice-Hall, 2a edición, 2002.
  • M. Spivak. Cálculo en variedades. Editorial Reverté, 2a edición, 1970.
  • W. A. Sutherland, Introduction to metric and topological spaces, 2nd edition, Oxford University Press, 2009.

Software

The projects for lab assessment will be programmed in Python.