Grafové algoritmy

V zimním semestru 2012/2013 přednáším Grafové algoritmy. Přednáška se koná v úterky od 12:20 v S4.

datum co se přednášelo
9. 10. Toky v sítích: formulace, základní věty, Fordův-Fulkersonův algoritmus, Dinicův algoritmus.
16. 10. Toky v sítích: Dinicův algoritmus a důkladná analýza jeho všelijakých variant. 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. Zpřesňovací algoritmus pro celočíselné kapacity. Algoritmus Tří Indů.
23. 10. Hledání nejmenšího z řezů v celém grafu pomocí toků. Nejmenší řez pravděpodobnostně (Karger-Stein). (přednášel Milan Straka)
30. 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. Datové struktury pro Dijkstrův algoritmus: různé druhy hald, přihrádkové struktury.
6. 11. Nejkratší cesty: další datové struktury pro Dijkstru – víceúrovňové přihrádky, zmínka o HOT queues a ekvivalenci mezi tříděním a monotónními haldami. Dinicův trik. Potenciálová redukce a eliminace záporných hran. Heuristiky na hledání cest mezi zadanou dvojicí vrcholů (algoritmus A*).
13. 11. 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.
20. 11. Transitivní uzávěr metodou Rozděl a panuj. Seidelův algoritmus pro vzdálenosti v neohodnocených neorientovaných grafech. Ú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.
27. 11. Červeno-modrý pohled na Jarníkův, Borůvkův a Kruskalův algoritmus. 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.
4. 12. Hustota minorově uzavřených tříd: Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu. Minimální kostry ještě jednou: Fredmanův-Tarjanův algoritmus (iterovaná verze Jarníkova algoritmu).
11. 12. Testování rovinnosti grafů a kreslení grafů do roviny. Předehra: hledání mostů a artikulací prohledáváním do hloubky.
18. 12. Pokračování rovinného kreslení (slidy): doplnění detailů potřebných pro lineární čas, důkaz korektnosti (nekompletní, opravená verze se objeví ve skriptíčkách). Stromoví předchůdci (LCA), intervalová minima (RMQ) a dekompozice na bloky.
8. 1. Suffixové stromy, jejich vlastnosti a Ukkonenův algoritmus pro jejich konstrukci v lineárním čase. Převod řetězcových problémů na grafové. (Do online verze skriptíček jsem dopsal lepší popis Ukkonenova algoritmu.)

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š