MM856: Graph theory

The Study Board for Science

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N310057102
Assessment: Second examiner: Internal
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master

STADS ID (UVA): N310057101
ECTS value: 10

Date of Approval: 22-04-2025


Duration: 1 semester

Version: Approved - active

Entry requirements

MM856 is taught as part of MM855, and one can therefore only sign up for one of these courses.

Academic preconditions

Students taking the course are expected to have basic knowledge of graph theory and discrete mathematics, corresponding to the material in the course MM541 (Combinatorial Mathematics).

Course introduction

The aim of the course is to enable the student to review definitions and results from graph theory, which is important in regard to identify mathematical structures from graph theory in concrete examples.

Expected learning outcome

The learning objectives of the course are that the student demonstrates the ability to:
  • review definitions and results from graph theory.
  • use the theory to solve concrete problems.
  • give coherent solutions, arguing why the individual steps hold.
  • carry out complete proofs for results from the course curriculum.
  • explain connections between results and concepts in graph theory.
  • Use graph algorithms in order to solve complex problems.

Content

The following main topics are contained in the course: Graphs, trees, distances, matchings in general graphs, paths, cycles, colouring in graphs, Hamilton cycles, planar graphs, random graphs, NP-hardness and directed graphs.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn and January

Tests

Portfolio and tests

EKA

N310057102

Assessment

Second examiner: Internal

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Duration

3 hours

Examination aids

All common aids are allowed e.g. books, notes and computer programmes which do not use internet etc. 

Internet is not allowed during the exam. However, you may visit the course site in itslearning to open system "DE-Digital Exam". If you wish to use course materials from itslearning, you must download the materials to your computer no later than the day before the exam. During the exam you cannot be sure that all course materials is accessible in itslearning. 

ECTS value

10

Additional information

Portfolio exam consisting of two parts:

  • Compulsory assignments - weighted 20%
  • Written examination (January) - weighted 80%

The reexam will be in the form of a written exam.

Indicative number of lessons

90 hours per semester

Teaching Method

Planned lessons
Total number of planned lessons: 90
Hereof:
Common lessons in classroom/auditorium: 90
These classes consist of lectures and problem solving.

Other planned teaching activities:
Study the course material and prepare for the weekly exercises, individually or through group work.

Teacher responsible

Name E-mail Department
Anders Yeo yeo@imada.sdu.dk Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.