Text

Course syllabus - Graph Theory, Networks and Applications

Scope

7.5 credits

Course code

MAA600

Valid from

Autumn semester 2026

Education level

Second cycle

Progressive Specialisation

A1N (Second cycle, has only first-cycle course/s as entry requirements)

Main area(s)

Mathematics/Applied Mathematics

Organisation

Department of Business and Mathematics

Ratified

2014-03-05

Revised

2025-11-03

Literature lists

Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.

Objectives

The objective of this course is to present the core concepts and methods of graph theory and to develop, within this context, the student's ability to handle logic, algorithms, modelling, and computations in a meaningful way.

Learning outcomes

Upon completion of the course the student is expected to be able to

  • correctly account for the core examples, ideas, and concepts of graph theory
  • apply basic graph-theoretical theorems
  • apply algorithms for solving certain standard graph-theoretical problems
  • state general mathematical problems in graph-theoretical language
  • apply standard transformations of graph-theoretical problems to make them more tractable
  • apply concepts and methods of graph theory within computer science and information technology

Course content

  • simple graphs, multigraphs, pseudographs, and digraphs
  • paths, cycles, connectivity, and distance in graphs
  • algorithms for the shortest distance in graphs
  • trees, bipartite graphs, and other elementary classes of graphs
  • matchings
  • algorithms for finding matchings in graphs
  • vertex- and edge-colouring
  • networks and flows
  • encodings of graphs and algorithmic aspects of these

Specific requirements

At least totally 120 credits in the engineering, natural sciences, business administration or economics areas of which at least 60 credits within the engineering and natural science area including 30 credits mathematics/applied mathematics in which Basic Vector Algebra, 7.5 credits, and Discrete Mathematics, 7.5 credits, or equivalent is included. In addition, Swedish course 3 or Swedish level 3 and English course 6 or English level 2 are required. For courses given entirely in English exemption is made from the requirement in Swedish course 3 or Swedish level 3.

Examination

Examination (TEN2), 4 credits, 3, 4 or 5
Project (PRO1), 3,5 credits, 3, 4 or 5

A student who has a certificate from MDU regarding disability study support, can request adaptions for the examination. It is the examiner who takes decisions on any adaptions, based on the certificate and other conditions.

Grade

Grading scale: 5, 4, 3