Grafové algoritmy

V zimním semestru 2010/2011 přednáším Grafové algoritmy. Přednáška se koná každé úterý od 14:00 v S4.

datum co se přednášelo
12. 10. Toky v sítích: formulace, základní věty a Fordův-Fulkersonův algoritmus. Převod k-souvislosti na toky v sítích, Mengerova věta a související algoritmické úlohy. Dinicův algoritmus.
19. 10. Toky v sítích: Různé varianty Dinicova algoritmu a jejich analýza. Důsledky pro úlohy o řezech a párováních. Zmínka o Gomoryho-Huových stromech. Perfektní párování v regulárním bipartitním grafu pomocí redukce stupňů, souvislost s hranovým barvením.
26. 10. Minimální řez pravděpodobnostně (Karger-Stein). Nejkratší cesty: základní věty a relaxační algoritmus.
2. 11. Nejkratší cesty: Dijkstrův algoritmus a datové struktury pro něj: různé druhy hald, přihrádkové struktury, víceúrovňové přihrádky. (Najdete o nich novou kapitolu ve skriptíčkách.)
9. 11. Nejkratší cesty: potenciálové redukce, heuristiky na hledání cest mezi zadanou dvojicí vrcholů (algoritmus A*). Výpočet matice vzdáleností: Floydův-Warshallův algoritmus (a jeho zobecnění na regulární výrazy), využití násobení matic: dosažitelnost a Seidelův algoritmus pro neohodnocené neorientované grafy.
16. 11. Dosažitelnost a nejkratší cesty metodou Rozděl a panuj. Úvod do minimálních koster: základní věty o struktuře (výměny, jednoznačnost, charakterizace pomocí lehkých hran). Červeno-modrý algoritmus a jeho dualita.
23. 11. Minimální kostry v rovinných grafech a minorově uzavřených třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Odhady hustoty minorově uzavřených tříd (Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu).
[Není ve skriptíčkách, ale podívejte se do mé disertace, kapitola 3.1.]
30. 11. Minimální kostry ještě jednou: Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald (Fredman-Tarjan). Union-Find aneb inkrementální udržování komponent souvislosti.
7. 12. Dekompozice problémů: stromoví předchůdci (LCA) a intervalová minima (RMQ). Union-Find s předem známým stromem Unionů pomocí Fredericksonovy clusterizace.
14. 12. Suffixové stromy, jejich vlastnosti a Kärkkainenův-Sandersův algoritmus pro jejich konstrukci v lineárním čase. Převod řetězcových problémů na grafové.
21. 12. Datová struktura pro dynamické udržování komponent souvislosti (Holm-de Lichtenberg-Thorup).
[Není ve skriptíčkách, najdete ji v kapitolách 5.2 a 5.3 disertace.]
4. 1. Testování rovinnosti grafů a kreslení grafů do roviny. Předehra: hledání mostů a artikulací prohledáváním do hloubky.
[Povídám trochu jinak, než je ve skriptíčkách. Postupně je upravím. Zatím aspoň stručné slidy z přednášky.]
11. 1. Pokračování rovinného kreslení: doplnění detailů potřebných pro lineární čas, důkaz korektnosti. Jako zákusek servírovány van Emde-Boasovy stromy.

Zkoušky

Zkouším každou středu ve zkouškovém období od 10:00 a od 14:00 (přihlašte se, prosím, v SISu), pokud by se vám to více hodilo jindy, ozvěte se mi.

Ke zkoušce byste měli znát odpřednesené a umět to aplikovat. Rozbor případů v důkazu algoritmu na rovinné kreslení zkouším pouze na přání ;)

Literatura

Stránku spravuje Martin Mareš