MM810: Graph Theory I (5 ECTS)

STADS: 13004201

Level
Master's level course approved as PhD course

Teaching period
The course is offered when needed.

Teacher responsible
Email: qin@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None.

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

Subject overview
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

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Report and oral examination. The report is assessed as part of the oral examination. Allowed exam aids: Books and notes during preparation time before the oral exam. Grades according to the Danish 7-mark scale and external marking.

Reexamination according to the rules approved by the Study Board.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 22 hours
Skills training phase: 20 hours, hereof:
 - Tutorials: 20 hours

Educational activities

Educational form
Activities during the study phase: To study the course material and prepare for the weekly exercises, individually or through group work.

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.