Grafové algoritmy

V zimním semestru 2017/2018 přednáším o grafových algoritmech. Přednáška bude pokrývat pokročilejší algoritmy pro nejkratší cesty, toky v sítích, minimální kostry a další grafové problémy a také v ní zmíníme některé datové struktury pro dynamickou reprezentaci grafů.

Přednáška se koná každé pondělí od 17:20 v S4.

datum co se přednášelo
9. 10. Toky v sítích: základní definice a věty, Fordův-Fulkersonův algoritmus, symetrická formulace toku, dualita toků a řezů. 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.
16. 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.
23. 10. Nejmenší řezy a separátory v neorientovaných grafech pomocí toků. Pravděpodobnostní algoritmus Kargera a Steina.
30. 10. Ú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. Červeno-modrý pohled na Jarníkův, Borůvkův a Kruskalův algoritmus.
6. 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). Hustota minorově uzavřených tříd: Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu.
13. 11. Minimální kostry: Jarníkův algoritmus s Fibonacciho haldou, Fredmanův-Tarjanův algoritmus (iterovaná verze Jarníkova algoritmu). Nejkratší cesty: definice, problémy se zápornými cykly, prefixová vlastnost a stromy nejkratších cest.
20. 11. Nejkratší cesty: Obecný relaxační algoritmus a důkaz jeho korektnosti. Bellmanův-Fordův a Dijkstrův algoritmus coby speciální případy relaxace.
27. 11. Datové struktury pro Dijkstrův algoritmus: různé druhy hald, přihrádky, víceúrovňové přihrádky, zmínka o HOT queues. Dinicův trik pro neceločíselné délky hran. Potenciálová redukce a eliminace záporných hran. Heuristiky na hledání cest mezi zadanou dvojicí vrcholů (algoritmus A*).
4. 12. 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í. Sledy očima algebraikovýma.
11. 12. Transitivní uzávěr metodou Rozděl a panuj. Seidelův algoritmus pro vzdálenosti v neohodnocených neorientovaných grafech. Stromoví předchůdci (LCA), intervalová minima (RMQ) a dekompozice na bloky. Zmínka o Fredericksonově clusterizaci.
18. 12. Suffixové stromy a jejich vlastnosti. Převod řetězcových problémů na grafové. Suffixová pole a LCP pole, ekvivalence se suffixovými stromy a Kärkkäinenův-Sandersův algoritmus pro jejich konstrukci v lineárním čase.
8. 1. Testování rovinnosti grafů a kreslení grafů do roviny (Boyer-Myrvoldová). Předehra: bloková struktura grafu a její konstrukce prohledáváním do hloubky. Kreslení grafu v obráceném DFS pořadí. Detaily potřebné pro lineární čas. (Bez důkazu korektnosti. Pozor, ten ve skriptíčkách je špatně, pokusím se ho během zkouškového opravit.)

Zkoušky

Termíny budou 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š