PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Grafové minory a stromové rozklady - NDMI059
Anglický název: Graph Minors and Tree Decompositions
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Jiří Fiala, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: T_KAM (15.05.2003)

Kurz zaměřený na teorii grafových minorů a zvláště na aplikace souvisejícího pojmu stromového zdvihu pro návrh algoritmů. Vhodné pro studenty mat. a inf. od 3.r. i pro doktorandy (M a I).
Literatura
Poslední úprava: FIALA (15.03.2006)

Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.

Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.

Časopisecká literatura podle specifikace přednášejícího. K dipozici budou též poznámky přednášejícího v angličtině.

Sylabus -
Poslední úprava: FIALA/MFF.CUNI.CZ (08.04.2010)

Na kurzu bude probrán úvod do teorie grafových minorů a dobrých kvaziuspořádání, m.j. bude dokázána Kruskalova věta o dobrém kvaziuspořádání na třídě konečných stromů. Těžiště kurzu je založeno na pojmu stromového zdvihu a na jeho vztahu k teorii grafových minorů.

 
Univerzita Karlova | Informační systém UK