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
Censorship: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master

STADS ID (UVA): N310001101
ECTS value: 5

Date of Approval: 25-04-2019


Duration: 1 semester

Version: Approved - active

Comment

13004201(former UVA) is identical with this course description. 

Entry requirements

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

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

See Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn

Tests

Report and oral examination

EKA

N310001102

Censorship

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.

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

Indicative number of lessons

42 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.

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
Jing Qin qin@imada.sdu.dk

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period