|
|
|
||
Úvodní kurz teorie matroidů - definice matroidů (nezávislé množiny, báze, kružnice, ranková funkce), operace na
matroidech (dualita a minory), souvislost matroidů, třídy matroidů a jejich reprezentace.
Poslední úprava: T_KAM (18.04.2010)
|
|
||
Na zápočet je potřeba získat 2/3 bodů z aktivity na cvičení. Body je možné doplnit domácími úkoly.
Zápočet je nutnou podmínkou pro konání zkoušky. Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (26.02.2019)
|
|
||
D.Král', O.Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI series 430 (2009). Oxley:Matroid theory Truemper: Matroid decomposition Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)
|
|
||
Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních.
Zkouška má obvykle ústní podobu s možností písemné přípravy. Zápočet je podmínkou pro konání zkoušky.
Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (14.02.2019)
|
|
||
Definice a základní příklady. Dualita a minory. Souvislost matroidů a vztah ke grafové souvislosti. Matroid intersection theorem a jeho aplikace. Reprezentovatelnost, reprezentovatelné, binární a regulární matroidy. Grafové matroidy. Algoritmické aspekty matroidových problémů. Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)
|