MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2010
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.
Rozvrh
Čt 9:00–11:50 B411
Předpoklady
Teorie grafu MA010 (Graph theory). 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á 19 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, planar graphs, colourings.
  • The Kuratowski 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.
  • Complexity of the graph crossing number problem.
  • Crossing-critical graphs and their structure.
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/Teaching/AGTT.html
Course based on the book * Mohar, Bojan - Thomassen, Carsten. Graphs on Surfaces.
Supplementary literature (in Czech): Petr Hliněný. Teorie grafů, "http://www.fi.muni.cz/~hlineny/Vyuka/GT/".
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 2012, jaro 2014.