## M5140 Graph Theory

Faculty of Science
autumn 2021
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).
Taught partially online.
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
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
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. I, Grafy. 1. vyd. Praha: Státní pedagogické nakladatelství, 1983. 173 s. info
• NEŠETŘIL, Jaroslav. Teorie grafů [Nešetřil, 1979]. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1979. 316 s. info
• PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983. 343 s. info
• KUČERA, Luděk. Kombinatorické algoritmy. 2. vyd. Praha: Státní 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)
The course is taught annually.
The course is taught: every week.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2007 - for the purpose of the accreditation, Autumn 1999, Autumn 2010 - only for the accreditation, Autumn 2000, Autumn 2001, Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020.
• Enrolment Statistics (recent)