PřF:M5140 Graph Theory - Course Information

M5140 Graph Theory

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:

M5140/01: Mon 14:00–14:50 M2,01021, 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

• Applied Informatics (programme FI, B-AP)
• Applied Informatics (programme FI, N-AP)
• Applied Mathematics for Multi-Branches Study (programme PřF, B-MA)
• Mathematics - Economics (programme PřF, B-AM)
• Mathematics (programme PřF, B-MA)
• Profesional Mathematics (programme PřF, B-MA)

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

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)  

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