Přednáška NMIN331 probíhá v Pondělí 10:40 v K8, přednáší prof. Jan Kratochvíl a Tomáš Gavenčiak. Pro představu o chystané látce viz stránku loňské přednášky.

Cvičení navazuje ve 12:20 tamtéž, cvičí Martin Balko. Více viz stránky cvičení.

Minulou přednášku vedl Pavel Valtr, stránka přednášky zde.

Literatura

[KzDM] J. Matoušek, J. Nešetřil: Kapitoly z diskretní matematiky

[KaG] T. Valla, J. Matoušek: Kombinatorika a grafy I [online]

Zkoušky

Zkoušky se zkládají z písemné přípravy na přiděleně téma a následné ústní části. Jsou vypsány tyto termíny:

  • Úterý 5. 6. 14:00, S 226 (pracovna prof. Kratochvíla) [SIS]
  • Čtvrtek 21. 6. 9:00, S 226 (pracovna prof. Kratochvíla) [SIS]
  • Úterý 26. 6. 9:00, S 226 (pracovna prof. Kratochvíla) [SIS]

Probraná látka

Přednáška 19. 2. (JK, MB)

Matice sousednosti grafu, mocniny matice sousednosti a počet sledů v grafu. Laplacián grafu a počet koster grafu pomocí determinantu Laplaciánu.

Přednáška 26. 2. (TG, MB)

Obyčejné vyrvořující funkce a jejich aplikace. Definice vytvořujících funkcí a operací nad nimi včetně derivace, integrálu a konvoluce. Odvození vytvořujících funkcí přímou sumací, operacemi nad známými vyvořujícími funkcemi a z funkcionálních rovnic (například pro posloupnost ). Význam konvoluce v posloupnostech. Odvození vytvřující funkce a explicitního vzorce pro Fibonacciho posloupnost.

Zdroj: [KzDM] Sekce 10.1 - 10.3.

Přednáška 5. 3. (2x MB)

Pokračování o vytvořujících funkcích. Zobecněná binomická věta, počítání binárních stomů, uzávorkování a další cvičení. Viz též stránky cvičení.

Zdroj: [KzDM] Sekce 10.4 - 10.5.

Přednáška 12. 3. (2x JK)

Toky v sítích: definice, řezy a elementární řezy, věta o dualitě, Ford-Fulkersonův algoritmus a důkaz korektnosti pro racionální kapacity, topologický důkaz existence maximálniho toku i pro reálné kapacity, věta o existenci celočíselného maximálního toku při celočíselných kapacitách.

Hallova věta a systémy různých reprezentantů (důkaz přes toky v sítích). Věta o párování v bipartitiním grafu (všechny stupně jedné partity alespoň takové jako všechny stupně druhé partity implikuje perf. párování), důsledek o perf. párováních v regulárních bipartitních grafech.

Zdroj: [KaG] Kapitoly 2 a 4.

Přednáška 19. 3. (2x TG)

Vcholová souvislost a hranová souvislost grafu, lemmata o monotonicitě při mazání hran, věta . Věty Ford-Fulkerson a Menger o vztahu hranové (resp. vrcholové) souvislosti a počtu hranově (resp. vrcholově) disjunktnich cest. Důkaz Königovy věty o vrcholovém pokrytí v bipartitním grafu pomocí toků v síti.

Zdroj: [KaG] Kapitola 3.

Cvičení: Algoritmus Ford-Fulkerson může běžet libovolně dlouho (s vahami v ) či nekonečně douho (s vahami v , viz Wikipedia). Doplňování latinských obdélníků na latinské čtverce. Dvojitě stochastická matice je afinní kombinací permutačních matic. Stabiní párování (stable marriage), existence a algoritmus.

Přednáška 26. 3. (TG, MB)

Tutteho věta, Tutte-Berge formule (viz Wikipedia, důkaz z Tutteho přidáním univerzálních vrcholů a nalezením perfektního párování). Alternativní (přímý) důkaz Tutte-Berge popisuje D. West, Tutte z něj plyne přímo. Gallai-Edmonds o struktuře maximálních párování (jen tvrzení a intuice; nebude zkoušeno).

Zroj: [KaG] Sekce 5.1, D. B. West: A short proof of the Berge–Tutte Formula and … [PDF]

Přednáška 2. 4. Není

Velikonoční pondělí.

Přednáška 9. 4. (TG, MB)

Rovinné grafy: definice křivky a oblouku, nakreslení grafu oblouky a lomenými oblouky, ekvivalence existence obloukového a lomenicového nakreslení (náznak důkazu). Jordanova věta [Wiki] bez důkazu.

Eulerova formule (s náznakem topologického důkazu z Jordanovy věty), max. počet hran rovinného grafu (a z toho 5-degenerovanost) a rovinného grafu bez rojúhelníků. Nerovinnost a jako důsledek Eulerovy formule. Rovinnost je uzavřená na podgrafy, dělení hran a kontrakce hran. Kuratowského věta (jednodušší implikace plyne z předchozího).

Barevnost grafu, duál rovinného grafu a barevnost duálu (obarvení mapy), věta o 4 barvách (bez důkazu), věta o 5 barvách (dokázáno).

Zdroj: [KzDM] Kapitola 6.

Přednáška 16. 4. (JK, MB)

Bloková struktůra grafu, ušaté lemma o vytváření 2-souvislých grafů.

Zdroj: [KzDM] Sekce 3.8. (neúplný)

Přednáška 23. 4. (JK, MB)

Hamiltonovské kružnice grafu, Chvátalův uzávěr a postačující podmínky hamiltonovskosti, lízátkový graf, Smith-Thomasson věta o sudosti počtu ham. kružnic v grafech s pouze lichými stupni. 2-aproximační algoritmus pro metrický TSP.

Zdroj: [KG] Kapitola 6 (krom S-T a lízátkového grafu)

Přednáška 30. 4. (2x JK)

Edmondsův algoritmus pro párování v obecných grafech: volné stříavé cesty, lemma o kontrakci “květů”, Edmondsovy lesíky a následně algoritmus s důkazem správnosti (bez časové složitosti).

Zdroj: [KG] Sekce 5.2.

Ramseyovy věty: symetrické a nesymetrické pro dvě barvy , odhad , odhad , Schurovo lemma. Ramsey pro -tice (nebude zkoušen).

Zdroj: [KG] Kapitola 1, [KzDM] Kapitola 11.

Přednáška 7. 5. (2x MB)

Dvojcvičení k přednášce 30. 4.

Přednáška 14. 5. (TG, MB)

Úvod do vyčíslitelnosti: definice problému jako jazyka, definice rekurzivních a rekurzivně vyčíslitelných jazyků, halting problém a jeho nerozhodnutelnost. Definice výpočetních modelů: Turingův stroj a Random access machine a náznak jejich ekvivalence. Univerzální Turingův stroj. Další problémy ekvivalentní s halting problémem: dokazatelnost, Diofantické rovnice, Postův korespondenční problém.

Zrdoj: Skripta P. Kučery [PDF]

Přednáška 21. 5. (TG, MB)

Definice tříd P, NP a co-NP pomocí nedeterministického Turingova stroje a pomocí existence “certifikátu” náležení do jazyka, NP-těžkost a NP-úplnost, připomenutí převodu mezi problémy (formálně jako jazyky). Zavedení základních NP-úplných problému: SAT, 3-SAT, -barevnost grafu, Hamiltonovská kružnice, obchodní cestující, největší klika a nezávislá množina. Kontrast s podobnými problémy, které jsou v P (prvočíselnost, 2-barevnost). Důkaz Cook-Levinovy věty (SAT je NP-úplný problém) převodem výpočtu Turingova stroje s certifikátem na formuli popisující jeho výpočet.

Na cvičení byly přiklady dalších převodů. Na zkoušce bude očekávána znalost alespoň jednoho netriviálního převodu mezi NP-úplnými problémy.

Zdroj: Skripta Úvod do složitosti a NP-úplnosti V. Majerecha [online]