Krajinou grafových algoritmů

(průvodce pro středně pokročilé)

Na této stránce naleznete skriptíčka k mé přednášce z grafových algoritmů. Text vychází ze zápisků účastníků semináře z grafových algoritmů z roku 2006 (díky vám!) a od té doby prošel mnoha revizemi a doplněními, takže by měl pokrývat i současný rozsah přednášky a něco málo navíc. Připomínky a upozornění na chyby více než vítány na adrese mj@ucw.cz.

Skriptíčka už také vyšla tiskem v ITI Series (ISBN 978-80-239-9049-2). Měla by být k nalezení v informatickém oddělení fakultní knihovny, případně u nás na Katedře aplikované matematiky. Tištěná podoba odpovídá verzi 2007-03-13, kterou si můžete stáhnout jako PDF.

Do tištěné verze se vloudilo několik chyb, opravte si je, prosím.

Skriptíčka stále udržuji, níže jsou novější verze některých kapitol. Můžete si zkusit stáhnout aktuální verzi celých skriptíček. Sazba není tak vyladěná, jako u tištěné verze, ale text je rozhodně lepší. Celý text bydlí v Gitové repository na git://git.ucw.cz/ga.git/, můžete si prohlédnout historii změn.

V říjnu 2009 přibyla nová zbrusu kapitola o pravděpodobnostních algoritmech na hledání minimálního řezu, na přelomu roků 2010 a 2011 další dvě kapitoly o nejkratších cestách.

Obsah

kapitola verze obsah
0. Úvod 2010-10-26 Úvod a poděkování. Základní značení.
1. Toky a řezy 2013-04-10 Toky v sítích: formulace, základní věty a algoritmy. Převod bipartitního párování a k-souvislosti na toky.
2. Dinicův algoritmus 2010-10-26 Důkladná analýza Dinicova algoritmu a různých jeho variant. Škálovací algoritmus pro celočíselné kapacity. Algoritmus tří Indů.
3. Párování a k-souvislost 2010-10-26 Perfektní párování v regulárním bipartitním grafu pomocí štěpení grafů. Vrcholová/hranová k-souvislost pomocí toků. Globální minimální řez (Nagamochi-Ibaraki).
4. Gomory-Hu Trees 2010-10-26 Gomory-Hu Trees: Datová struktura pro efektivní popis všech minimálních řezů v grafu. Základní vlastnosti a algoritmus pro efektivní konstrukci.
5. Minimální kostry 2014-01-23 Minimální kostry: základní věty o struktuře MST. Červeno-modrý algoritmus a jeho analýza. Důkazy korektnosti všech klasických algoritmů zdarma.
6. Kostry podruhé 2013-01-21 Minimální kostry v rovinných grafech a obecněji v minorově uzavřených třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald.
7. Počítání na RAMu 2014-01-23 Výpočetní modely. Počítání na RAMu (triky s bitovými operacemi a násobením; jak udělat z normálního procesoru vektorový). Van Emde-Boasovy stromy.
8. Q-Heaps 2010-10-26 Bitově paralelní B-stromy. Q-Heaps a minimální kostra pro celočíselné váhy hran v lineárním čase.
9. Dekompozice stromů 2014-02-25 Union-Find problem a jeho varianta s předem známou posloupností Unionů. Fredericksonova clusterizace a micro/macro-tree dekompozice. Hledání stromových předchůdců a intervalových minim.
10. Suffixové stromy 2014-01-23 Suffixové stromy, jejich vlastnosti a dva lineární algoritmy pro jejich konstrukci (rekurzivní a inkrementální). Převod řetězcových problémů na grafové.
11. Rovinné grafy 2012-01-03 Testování rovinnosti a kreslení grafů do roviny.
12. Pravděpodobnostní algoritmus na řezy 2010-10-26 Nahlédnutí do říše pravděpodobnostních algoritmů: Kargerův-Steinův algoritmus na hledání minimálního řezu.
13. Nejkratší cesty 2014-01-23 Nejkratší cesty: Základní věty, obecný relaxační algoritmus a různé jeho verze. Dijkstrův algoritmus a datové struktury pro něj (haldy, přihrádkové struktury a jejich kříženci). Potenciálová redukce délek a algoritmus A*.
14. Transitivní uzávěry 2013-01-21 Algoritmy pro výpočet transitivního uzávěru – matice vzdáleností a matice dosažitelnosti. Floydův-Warshallův algoritmus a jeho zobecnění pro konstrukci sledových regulárních výrazů. Souvislost s různými druhy násobení matic. Použití metody Rozděl a panuj. Seidelův algoritmus.
Stránku spravuje Martin Mareš