MM855: Introduction to Graph Theory

Study Board of Science

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

STADS ID (UVA): N310055101
ECTS value: 5

Date of Approval: 13-05-2020


Duration: 1 semester

Version: Archive

Comment

MM855 is taught as part of MM856, and one can therefore only sign up for one of these courses.
Note that MM855 is run in the first half of the fall semester.

Entry requirements

None

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 and directed graphs.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

January

Tests

Written exam

EKA

N310055102

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

Allowed (Except internet). A closer description of the exam rules will be posted under 'Course Information' on Blackboard.

ECTS value

5

Additional information

The examination form for re-examination may be different from the exam form at the regular exam.

Indicative number of lessons

45 hours per semester

Teaching Method

The teaching method is based on three phase model.
  • Intro phase (lectures, question classes): 30 hours.
  • Skills training phase (exercise sessions): 15 hours.
  • Total = 45 hours.
Activities during the study phase: To 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 Institut for Matematik og Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period