#
PřF:M5140 Graph Theory - Course Information

## 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**- 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. 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

- NEŠETŘIL, Jaroslav.
**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**- FI:
**MA010**Graph Theory

!PřF:M5140&&!NOW(PřF:M5140)

- FI:

- Enrolment Statistics (recent)

- Permalink: https://is.muni.cz/course/sci/autumn2021/M5140