M5140 Graph Theory

Faculty of Science
Autumn 2019
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
Wed 12:00–13:50 M5,01013
  • Timetable of Seminar Groups:
M5140/01: Wed 14:00–14:50 M5,01013, M. Kunc
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. 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
Examination written (pass mark 50%) and oral.
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
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 2020, autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2019, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2019/M5140