DRL032 Graph Theory with Applications in Logistics (Autumn 2025)

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

This course would meet the criterion related to methodology-content of the course package if you are registered to the PhD Logistics program at Molde University College

30 h lectures. All lectures are mandatory.

One daily exercise must also be approved.

Submission of a course paper within two weeks after the course.

Grading scale: Pass / Fail