MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2008
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
St 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á 20 mateřských oborů, zobrazit
Cíle předmětu
Rovinné grafy a grafy kreslené na vyšších plochách hrají (poněkud překvapivě) velmi důležitou úlohu v teorii grafů a v jejích aplikacích. (Pro příklad zmíníme Větu a čtyřech barvách, projekt grafových minorů, či mnohé nedávné parametrizované algoritmy pro těžké grafové problémy.)
Náš předmět je pro studenty matematiky nebo teoretické informatiky úvodem do této krásné oblasti teorie grafů, která se také nazývá topologická teorie grafů. Naše přednášky shrnují důležité výsledky v této oblasti od klasické Kuratowského věty, přes větu o čtyřech barvách, až po nedávné strukturální výsledky spojené s projektem grafových minorů a po problém průsečíkového čísla.
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. ISBN 0-8018-6689-8. 2001. URL info
  • NEŠETŘIL, Jaroslav a Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press. xv, 410 s. ISBN 0-19-850207-9. 1998. info
Metody hodnocení
This is an advanced course, taught in English, and conducted quite informally (seminar-type). Evaluation by a written individual homework assignment (one), and 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 2010, jaro 2012, jaro 2014.