#
PřF:M5140 Graph Theory - Course Information

## M5140 Graph Theory

**Faculty of Science**

Autumn 2012

**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)

Mgr. Eva Janoušková, Ph.D. (seminar tutor)

Mgr. David Kruml, Ph.D. (seminar tutor) **Guaranteed by**- doc. RNDr. Josef Niederle, CSc.

Department of Mathematics and Statistics - Departments - Faculty of Science

Supplier department: Department of Mathematics and Statistics - Departments - Faculty of Science **Timetable**- Wed 8:00–9:50 M1,01017
- Timetable of Seminar Groups:

*M. Kunc*

M5140/02: Thu 15:00–15:50 M5,01013,*D. Kruml*

M5140/03: Fri 9:00–9:50 M4,01024,*D. Kruml*

M5140/04: Fri 8:00–8:50 M4,01024,*D. Kruml*

M5140/T01A: No timetable has been entered into IS.*E. Janoušková*

M5140/T01AA: No timetable has been entered into IS.*E. Janoušková* **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**- there are 6 fields of study the course is directly associated with, display
**Course objectives**- This is an introductory course in graph theory. 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**- Written and oral examination.
**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:

- Enrolment Statistics (Autumn 2012, recent)
- Permalink: https://is.muni.cz/course/sci/autumn2012/M5140