PředmětyPředměty(verze: 825)
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 do 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.
Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Zdeněk Dvořák, Ph.D. (15.02.2018)

Předmět je zakončen zápočtem a zkouškou. Zápočet bude získán za aktivní účast na cvičeních, zejména diskusi řešení úloh zadávaných na přednáškách a referáty studovaných článků; ve výjimečných případech lze nahradit individuálními konzultacemi. Povaha kontroly předmětu vylučuje opravné termíny. Získání zápočtu je podmínkou pro konání zkoušky, kromě výjimek (předtermíny) stanovených vyučujícím.

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.

Požadavky ke zkoušce -
Poslední úprava: doc. Mgr. Zdeněk Dvořák, Ph.D. (15.02.2018)

Zkouška proběhne ústní formou. Bude se skládat z 2-3 otázek na obecný přehled o látce probrané na přednáškách a podrobnější diskusi některého z předem zadaných témat z osnov přednášky.

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