Grafové algoritmy

V zimním semestru 2011/2012 přednáším Grafové algoritmy. Přednáška se koná ve středy od 10:40 v S11.

datum co se přednášelo
5. 10. Toky v sítích: formulace, základní věty, Fordův-Fulkersonův algoritmus. Převod párování v bipartitních grafech a k-souvislosti na toky v sítích, Mengerova věta a související algoritmické úlohy. Dinicův algoritmus.
12. 10. Toky v sítích: Dinicův algoritmus a důkladná analýza jeho všelijakých variant. Zpřesňovací algoritmus pro celočíselné kapacity. Algoritmus Tří Indů.
19. 10. Minimální řez pravděpodobnostně (Karger-Stein). Zmínka o Gomoryho-Huových stromech.
26. 10. Nejkratší cesty: definice, problémy se zápornými cykly, prefixová vlastnost a stromy nejkratších cest. Obecný relaxační algoritmus a důkaz jeho korektnosti. Bellmanův-Fordův a Dijkstrův algoritmus coby speciální případy.
2. 11. Datové struktury pro Dijkstrův algoritmus: různé druhy hald, přihrádkové struktury, víceúrovňové přihrádky, zmínka o HOT queues a ekvivalenci mezi tříděním a monotónními haldami. Potenciálová redukce a eliminace záporných hran.
9. 11. 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 konstrukci sledových výrazů. Využití maticového násobení, transitivní uzávěr metodou Rozděl a panuj.
16. 11. Nejkratší cesty: Seidelův algoritmus pro neohodnocené neorientované grafy. Ú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.
30. 11. Minorově uzavřené třídy: Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu. Minimální kostry ještě jednou: Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald (Fredman-Tarjan).
7. 12. Union-Find aneb inkrementální udržování komponent souvislosti, odhad s log*. Stromoví předchůdci (LCA), intervalová minima (RMQ) a dekompozice na bloky.
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. Dokončení suffixových stromů. O haldách: zbrklé a líné binomiální haldy a jejich reprezentace binárními stromy; Rank-Pairing haldy [viz článek].
4. 1. Testování rovinnosti grafů a kreslení grafů do roviny. Předehra: hledání mostů a artikulací prohledáváním do hloubky.
11. 1. Pokračování rovinného kreslení (slidy): doplnění detailů potřebných pro lineární čas, důkaz korektnosti.

Zkoušky

Termíny jsou vypsány v SISu, přihlašujte se prosím tam; 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š