PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Teorie grafových minorů - NDMI085
Anglický název: Graph minor theory
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Zdeněk Dvořák, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: T_KAM (04.05.2011)

V této přednášce vyložíme teorii grafových minorů založenou na výsledcích Robertsona a Seymoura, se zaměřením na nové trendy v této oblasti. Předpokládají se znalosti v rozsahu přednášky NDMI059 nebo NDMI073.
Literatura -
Poslední úprava: T_KAM (04.05.2011)

N. Robertson, P. Seymour, Graph Minors I-XXIII.

Ken-ichi Kawarabayashi, Paul Wollan: A shorter proof of the graph minor algorithm: the unique linkage theorem. STOC 2011, 687-694.

K. Kawarabayashi, S. Norin, R. Thomas, P. Wollan: K_6 minors in 6-connected graphs of bounded tree-width, manuscript.

N. Robertson, P. Seymour, R. Thomas: Hadwiger's conjecture for K_6-free graphs, Combinatorica 13 (1993), no. 3, 279-361.

Sylabus -
Poslední úprava: T_KAM (04.05.2011)

Vlastnosti grafů na plochách, stromové rozklady a struktura grafů bez zakázaného minoru, minorová relace definuje dobré uspořádání, testování existence disjunktních cest a minorů, struktura t-souvislých grafů bez K_t a souvislost s Hadwigerovou hypotézou.

 
Univerzita Karlova | Informační systém UK