MM810: Graph Theory I
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N310001102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master's level course approved as PhD course
STADS ID (UVA): N310001101
ECTS value: 5
Date of Approval: 25-04-2019
Duration: 1 semester
Version: Approved - active
Comment
The course is offered as needed and is not necessarily offered every year. Examination exams for MM810 are offered according to the following plan, when offered: Autumn (course Start september): ordinary Exam (January), first reexamination (March) and 2nd reexamination (June or August).
Entry requirements
Academic preconditions
Students taking the course are expected to have knowledge of linear algebra, and basic notions and methods from abstract algebra.
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 courses MM538, 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 scientific projects at a high level, and to manage work and development situations that are complex, unpredictable and that require new solving skills.
- 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
- argue for the single steps in the solutions of problems
- carry out complete proofs for results from the course curriculum (counting arguments, induction, indirect proofs, algorithmic proofs)
- explain connections between results and concepts in graph theory
- use mathematical notation from set theory, function theory and logic
- identify mathematical structures from graph theory in concrete examples
Content
The following main topics are contained in the course: Graphs, subgraphs, connected graphs, trees, nonseparable graphs, tree-search algorithms, complexity of algorithms, connectivity, stable sets and cliques, matchings, Hamilton cycles.
Literature
Examination regulations
Exam element a)
Timing
Autumn
Tests
Report and oral examination
EKA
N310001102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
5
Additional information
The report is assessed as part of the oral examination.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
In order to enable students to achieve the learning objectives for the course, the teaching is organised in such a way that there are 42 lectures, class lessons, etc. on a semester.
In order to enable students to achieve the learning objectives for the course, the teaching is organised in such a way that there are 42 lectures, class lessons, etc. on a semester.
These teaching activities are reflected in an estimated allocation of the workload of an average student as follows:
- Intro phase (lectures) - 22 hours
- Training phase: 20 hours
Activities during the study phase: To study the course material and prepare for the weekly exercises, individually or through group work.