MM855: Introduction to Graph Theory
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
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
- 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
- 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
Examination regulations
Exam element a)
Timing
Tests
Written exam
EKA
Assessment
Grading
Identification
Language
Duration
Examination aids
All common aids are allowed e.g. books, notes, 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 the day before the exam. During the exam you cannot be sure that all course materials is accessible in itslearning.
ECTS value
Indicative number of lessons
Teaching Method
- Intro phase (lectures, question classes): 30 hours.
- Skills training phase (exercise sessions): 15 hours.
- Total = 45 hours.