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 | 2015-02-02 | 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 | 2014-10-16 | 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 | 2024-01-15 | 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é | 2016-01-28 | 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ů | 2015-01-31 | 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 | 2024-01-15 | Testování rovinnosti a kreslení grafů do roviny. |
| 12. Pravděpodobnostní algoritmus na řezy | 2017-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 | 2024-01-15 | 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 | 2024-01-13 | 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. |