MM810: Graph Theory I (5 ECTS)

STADS: 13004201

Level
Master's level course

Teaching period
The course is offered in the autumn semester.
According to needs.

Teacher responsible
Email: stephan.brandt@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal. 3. kvartal.

Prerequisites:
None

Academic preconditions:
Basic notions from linear algebra should be known, and basic notions and methods from abstract algebra should have been encountered.

Course introduction
To introduce basic notions and arguments from graph theory, including algorithmic aspects.

Expected learning outcome
At the end of the course the student will be able 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
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:
Oral examination, grades according to the danish 7-point scale and external censurship.

Reexamination according to the rules approved by the Study Board.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger:21 timer
Eksaminatotietimer/opgaveregning: 7 timer
Educational activities

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.