PřF:M5140 Graph Theory - Course Information
M5140 Graph Theory
Faculty of ScienceAutumn 2020
- Extent and Intensity
- 2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).
- Teacher(s)
- doc. Mgr. Michal Kunc, Ph.D. (lecturer)
- Guaranteed by
- doc. Mgr. Michal Kunc, Ph.D.
Department of Mathematics and Statistics – Departments – Faculty of Science
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science - Timetable
- Fri 8:00–9:50 M4,01024
- Timetable of Seminar Groups:
- Prerequisites (in Czech)
- ! M5145 Graph Theory && !( FI:MA010 Graph Theory )
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Applied Informatics (programme FI, B-AP)
- Applied Informatics (programme FI, N-AP)
- Applied Mathematics for Multi-Branches Study (programme PřF, B-MA)
- Course objectives
- This is an introductory course in graph theory.
- Learning outcomes
- After passing the course, students will be able to: use the basic notions of graph theory; define and understand basic properties of graphs, in particular, edge connectivity, vertex connectivity, planarity and chromatic number; explain and apply the most important results of graph theory; solve simple graph problems using standard effective algorithms.
- Syllabus
- Basic concepts: definition of graphs, basic graphs, representation of graphs, isomorphism of graphs, subgraphs, degree sequence.
- Walks, trails, paths: shortest paths, number of walks, Markov chains.
- Flow networks: max-flow min-cut theorem.
- Edge connectivity and vertex connectivity: connected components, bridges, Menger's theorem, 2-connected graphs, blocks, 3-connected graphs.
- Graph traversals: Eulerian graphs, Hamiltonian graphs, travelling salesman problem.
- Matchings: bipartite matching, Tutte's theorem.
- Trees: characterizations of trees, center, number of trees, minimal spanning trees.
- Edge colourings: bipartite graphs, Vizing's theorem, Ramsey's theorem.
- Vertex colourings: Brooks' theorem, chromatic polynomial.
- Planar graphs: Euler's formula, Platonic solids, Kuratowski's theorem, Fáry's theorem, dual graph, maximum number of edges, four colour theorem, genus.
- Minors: Robertson–Seymour theorem.
- Graph orientation: Robbins' theorem, tournaments.
- Literature
- NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1983, 173 s. URL info
- NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1979, 316 s. URL info
- PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983, 343 s. info
- KUČERA, Luděk. Kombinatorické algoritmy. 2., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury, 1989, 286 s. info
- Introduction to graph theory. Edited by Robin J. Wilson. 4th ed. Harlow: Prentice Hall, 1996, viii, 171. ISBN 0582249937. info
- DIESTEL, Reinhard. Graph theory. 3rd ed. Berlin: Springer, 2006, xvi, 410s. ISBN 3540261834. info
- Teaching methods
- Lectures and seminars.
- Assessment methods
- The examination consists of a compulsory written part (pass mark 50%) and an optional oral part. The requirements will be adjusted according to the epidemiological situation and current restrictions.
- Language of instruction
- Czech
- Further comments (probably available only in Czech)
- Study Materials
The course is taught annually. - Listed among pre-requisites of other courses
- FI:MA010 Graph Theory
!PřF:M5140&&!NOW(PřF:M5140)
- FI:MA010 Graph Theory
- Enrolment Statistics (Autumn 2020, recent)
- Permalink: https://is.muni.cz/course/sci/autumn2020/M5140