MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2012
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 13:00–15:50 G191m
Předpoklady
Graph Theory MA010. Introductory knowledge of topology is also welcome.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 30 stud.
Momentální stav registrace a zápisu: zapsáno: 0/30, pouze zareg.: 0/30, pouze zareg. s předností (mateřské obory): 0/30
Mateřské obory/plány
předmět má 20 mateřských oborů, zobrazit
Cíle předmětu
This subject introduces a mathematician or a theoretical computer scientist into the beauties of the topological graph theory. The lectures survey important results in this area, starting from classical ones like the Kuratowski theorem, through the Four Colour theorem, till recent structural results connected with the Graph Minor project, and the crossing number problem.
In this course the students will learn about some cutting-edge recent development in graph theory. At the end, they should: understand the basic principles of topological graph theory and of graph crossing numbers including algorithmic applications; and be able to continue with some scientific work in this area if they choose to.
Osnova
  • Basic graph terms, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's theorem, with a proof.
  • The Four Colour Theorem, with an outline of a proof.
  • Planarity algorithms and complexity.
  • Graphs embedded on higher surfaces.
  • Graph minors, tree-width, and "forbidden" characterizations.
  • The "Kuratowski" theorem for any surface.
  • Graphs drawings with edge-crossings. The crossing number problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (a seminar-type lecturing). Students are expected to actively participate in all the lectures and tutorials.
Metody hodnocení
Evaluation is based on a mandatory written individual homework assignment (one essay), and on a subsequent oral exam.
Vyučovací jazyk
Angličtina
Navazující předměty
Informace učitele
http://www.fi.muni.cz/~hlineny/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level.
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2014.