MM856: Graph theory
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N310057102
Censorship: Second examiner: Internal
Grading: 7point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master
STADS ID (UVA): N310057101
ECTS value: 10
Date of Approval: 13052020
Duration: 1 semester
Version: Approved  active
Comment
Entry requirements
MM856 is taught as part of MM855, and one can therefore only sign up for one of these courses.
Otherwise no further entry requirements.
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.
The course builds on the knowledge acquired in the course MM541, and gives an academic basis for studying further topics with the intent to write a thesis in discrete mathematics.
In relation to the competence profile of the degree it is the explicit focus of the course to:
 Give the competence to plan and execute complex scientific projects at a high level. This involves solving complex problems using tools from graph theory.
 Give skills to study, analyse, model and solve problems on a high level of abstraction using logical and structured argumentation.
 Give knowledge about advanced models and methods in graph theory.
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, NPhardness and directed graphs.
Literature
Examination regulations
Exam element a)
Timing
Autumn
Tests
Mandatory assignments and written exam
EKA
N310057102
Censorship
Second examiner: Internal
Grading
7point grading scale
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Duration
3 hours
Examination aids
Allowed(Except internet). A closer description of the exam rules will be posted under 'Course Information' on Blackboard.
ECTS value
10
Additional information
The final grade is based of an overall assesment (Mandatory assignment 20 % and written exam 80 %).
The examination form for reexamination may be different from the exam form at the regular exam.
Indicative number of lessons
Teaching Method
The teaching method is based on three phase model.
 Intro phase (lectures, question classes): 52 hours.
 Skills training phase (exercise sessions): 38 hours.
 Total = 90 hours.
Activities during the study phase: To study the course material and prepare for the weekly exercises, individually or through group work.
Teacher responsible
Timetable
31 
Monday
02082021

Tuesday
03082021

Wednesday
04082021

Thursday
05082021

Friday
06082021


08  09  
09  10  
10  11  
11  12  
12  13  
13  14  
14  15  
15  16 