MA051 Advanced topics in Graph Theory: Graphs on surfaces

Fakulta informatiky
jaro 2006
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 14:00–15:50 B411 a každý sudý čtvrtek 16:00–17:50 B411
Předpoklady
Běžné znalosti diskrétní matematiky a pojmu grafu. (Viz kniha "Kapitoly z diskrétní matematiky"). Vítány jsou i úvodní znalosti topologie.
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 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50, pouze zareg. s předností (mateřské obory): 0/50
Mateřské obory/plány
předmět má 7 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.
  • (A graph view of surface classification.)
  • 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
  • NEŠETŘIL, Jaroslav a Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410 s. ISBN 0-19-850207-9. info
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Vyd. 2., opr. Praha: Karolinum, 2000, 377 s. ISBN 8024600846. info
Metody hodnocení
Written individual homework assignment (one), and a subsequent oral exam.
Vyučovací jazyk
Angličtina
Informace učitele
http://www.fi.muni.cz/~hlineny/Teaching/AGTT.html
Další komentáře
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2008, jaro 2010, jaro 2012, jaro 2014.