Info
- Kontakt: vaclav.blazej (na) fit.cvut.cz
- Konzultace: Po domluvě emailem
- Kde mě najdete: NB 341b
GAK cvičení (pondělí, od 11:00).
- Informace a úkoly předmětu jsou na Course Pages ↗.
- Body za úkoly máte na Grades ↗
- za jednu sadu bude cca 12 bodů, celkem za semestr cca 150 bodů
- za 25 bodů zápočet
- za 60 bodů bude odpuštěna otázka u zkoušky (lehčí zkouška)
- za 100 bodů je automaticky dána známka A
- zkouška – 2 otázky z teorie, 1 na vyřesení úlohy
- zápočet za techování poznámek
Přehled témat
- Opakování pojmů z teorie grafů a kombinatoriky
- Generující funkce. -
- Barevnost kombinatorických struktur. - definice barevnosti, def barevnost na hypergrafech, first fit, k-degenerovaný => k+1 barevný, 5-color theorem?, bruxova veta - uplnak kruznicec nebo barevnost <= max stupen, k-barevnost je NP-complete? (perfektni, chordalni grafy)
- Úvod do Ramseyovy teorie. - základní, uniform hypergrafy a aplikace
- Lineární algebra v kombinatorice: věta o počtu koster. - viz Kapitoly, laplacova matice, determinant -> blempt a počet koster
- Úvod do pravděpodobnostní metody. - erdos dolni odhad na Ram číslo, něco na stř€dní hodnotu, Lovaszovo lokalní lemma a aplikace.
- Extremalní teorie grafů. - asi jen Turán pro grafy bez trojúhelníků
- Smith theorem - Hamiltonovsk€ kružnice, graf s lichými stupni – každou hranou prochází sudý počet ham kružnic
- Kuratowského věta (+ důkaz) a další otázky rovinnosti grafů.
- barevnost grafů na plochách obecného rodu
- hranová barevnost
- Vizingova věta - hranová barevnost <= delta+1
- Tutteova věta = perf párvoání ~ lich komponent je sudý; Edmondsův algoritmus - poly algo pro párování
- choosability - Thomassen theorem (planární stačí 5), konstrukce příkladu s 5 (lowerbound)
- Teorie nestranných kombinatorických her.