Teorie grafových minorů - NDMI085

• Anglický název: Graph minor theory
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 6
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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.

Poslední úprava: T_KAM (04.05.2011)

angličtina

The lecture covers the graph minor theory based on the results of Robertson and Seymour, with the emphasis on the new trends in this area. The knowledge of the results covered by NDMI059 or NDMI073 is assumed.

Poslední úprava: T_KAM (04.05.2011)

Podmínky zakončení předmětu

čeština

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.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (15.02.2018)

angličtina

Passing grade for tutorials (zápočet) is obtained on the basis of active participation, especially discussions of the solutions of the homework problems assigned during the lectures and presentations of studied papers; in exceptional cases, individual consultations can be used instead. The nature of these requirements precludes retakes. Passing grade for tutorials is required before taking the exam, this can be relaxed at the discretion of the lecturer in exceptional cases (early exam dates).

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (15.02.2018)

Literatura

čeština

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.

Poslední úprava: T_KAM (04.05.2011)

Požadavky ke zkoušce

čeština

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.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (15.02.2018)

angličtina

Oral exam consisting of 2-3 questions regarding general overview of topics covered by the lectures and a more detailed discussion of one of the topics, assigned in advance.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (15.02.2018)

Sylabus

čeština

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.

Poslední úprava: T_KAM (04.05.2011)

angličtina

Properties of graphs on surfaces, tree decompositions and the structure of the graphs without a forbidden minor, well-quasiordering by the minor relation, testing of existence of disjoint paths and of minors, the structure of t-connected graphs without K_t and the connection to Hadwiger conjecture.

Poslední úprava: T_KAM (04.05.2011)