- graphs and digraphs,
- graph algorithms, basic complexity terms (P, NP), construction of graphs,
- paths, cycles, connection,
- Eulerian and Hamiltonian cycles,
- colouring and covering,
- location problems on graphs,
- perfect graphs, efficient algorithms for chordal graphs,
- transitive hulls, irreducible kernels,
- trees, forests, matroids,
- search strategies: depth first search, breadth first search,
- matchings,
- planar graphs.
Module MAT-52-11-M-7
Graphs and Algorithms (M, 9.0 LP)
Module Identification
| Module Number | Module Name | CP (Effort) |
|---|---|---|
| MAT-52-11-M-7 | Graphs and Algorithms | 9.0 CP (270 h) |
Basedata
| CP, Effort | 9.0 CP = 270 h |
|---|---|
| Position of the semester | 1 Sem. irreg. |
| Level | [7] Master (Advanced) |
| Language | [EN] English |
| Module Manager | |
| Lecturers | |
| Area of study | [MAT-OPT] Optimisation |
| Reference course of study | [MAT-88.105-SG] M.Sc. Mathematics |
| Livecycle-State | [NORM] Active |
Courses
| Type/SWS | Course Number | Title | Choice in Module-Part | Presence-Time / Self-Study | SL | SL is required for exa. | PL | CP | Sem. | |
|---|---|---|---|---|---|---|---|---|---|---|
| 4V+2U | MAT-52-11-K-7 | Graphs and Algorithms
| P | 84 h | 186 h | - | - | PL1 | 9.0 | irreg. |
- About [MAT-52-11-K-7]: Title: "Graphs and Algorithms"; Presence-Time: 84 h; Self-Study: 186 h
Examination achievement PL1
- Form of examination: oral examination (20-30 Min.)
- Examination Frequency: each semester
- Examination number: 86240 ("Graphs and Algorithms")
Evaluation of grades
The grade of the module examination is also the module grade.
Contents
Competencies / intended learning achievements
Upon successful completion of this module, the students understand advanced graph theoretic methods to model and solve combinatorial problems and see their applications. They understand the structures of different graph classes and use this to construct efficient procedures. They can analyze the algorithms and apply them to solve practical problems. In addition, they can critically assess the possibilities and limitations of the use of these algorithms. They understand the proofs presented in the lecture and are able to reproduce and explain them. In particular, they can outline the conditions and assumptions that are necessary for the validity of the statements.
By solving the given exercise problems, they have gained a precise and independent handling of the terms, propositions and methods of the lecture. In addition, they have learnt to apply the methods to new problems, analyze them and develop solution strategies independently or ba team work.
Literature
- S. O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen,
- R. Diestel: Graph Theory,
- F. Harary: Graph Theory,
- M. R. Garey and D. S. Johnson: Computers and Intractability,
- T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to Algorithms.
Registration
Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de)
Requirements for attendance (informal)
Modules:
- [MAT-10-1-M-2] Fundamentals of Mathematics (M, 28.0 LP)
- [MAT-14-13-M-3] Linear and Network Programming (M, 9.0 LP)
Requirements for attendance (formal)
None
References to Module / Module Number [MAT-52-11-M-7]
| Course of Study | Section | Choice/Obligation |
|---|---|---|
| [INF-88.79-SG] M.Sc. Computer Science | Computer Science Theory | [WP] Compulsory Elective |
| [INF-88.79-SG] M.Sc. Computer Science | Formal Fundamentals | [WP] Compulsory Elective |
| [INF-88.79-SG] M.Sc. Computer Science | Specialization 1 | [WP] Compulsory Elective |
| Module-Pool | Name | |
| [INF-Alg_Ba_V-MPOOL-4] | Specialization Bachelor TA Algorithmics and Deduction | |
| [MAT-52-MPOOL-7] | Specialisation Mathematical Optimisation (M.Sc.) | |
| [MAT-AM-MPOOL-7] | Applied Mathematics (Advanced Modules M.Sc.) | |
| [MAT-RM-MPOOL-7] | Pure Mathematics (Advanced Modules M.Sc.) |