Facts about the course
- ECTS Credits:
- 5
- Responsible department:
- Faculty of Logistics
- Course Leader:
- Sebastian Alberto Urrutia
- Lecture Semester:
- Spring, Autumn
- Teaching language:
- English
- Duration:
- 1 week
DRL032 Graph Theory with Applications in Logistics (Autumn 2024)
About the course
Graph theory is a powerful tool for modeling many real-life problems including logistics problems such as scheduling, assignment, routing and network design.In this course we start by giving an introduction to graph theory concepts and applications. Special weight is given to the computational representation of graphs. Then, several classic problems in graph theory are studied in detail. Each problem is formally defined and several lemmas and theorems on properties of the problem at hand are proved. These lemmas and theorems then lead to algorithms to handle the studied problem.The course is neither wide (only a relatively small number of topics within graph theory are studied) nor deep (only some properties of each of the studied problems are investigated, with a clear focus on the development of algorithms).On the other hand, the course is formal. Each lemma and theorem presented is mathematically proven. In consequence, whenever an algorithm based on the proved statements is developed, its correctness follows from the correctness of the proved statements.The topics covered in the course are:
-
Basic notions on graphs and subgraphs.
-
Data structures for graphs representation.
-
Search algorithms in graphs and their applications.
-
Maximum matching in graphs
-
Cycles paths and shortest paths
-
Trees and Forests, Spanning trees
-
Eulerian Circuits.•Introduction to complexity theory
-
Examples of applications of graph theory to logistic problems.
The course will be offered in Week 45 2024 (Nov 4-8). The application deadline October 1 2024
The course is connected to the following study programs
Recommended requirements
Basic knowledge on logic, mathematics. Previous knowledge in algorithm design is a plus.
The student's learning outcomes after completing the course
The student should be able to identify when graph theory can be used to solve (part of) a problem in logistics and to implement the corresponding algorithms.
Forms of teaching and learning
One week of lecturing and presentations of research on graph theory and its applications, organized discussions on future applications and case studies involving graph theory.
Coursework requirements - conditions for taking the exam
30 h lectures. All lectures are mandatory.
One daily exercise must also be approved.
Examination
Submission of a course paper within two weeks after the course.
Grading scale: Pass / Fail