Grafové algoritmy

V zimním semestru 2015/2016 přednáším Grafové algoritmy. Přednášky se konají ve čtvrtky od 9:00 v S8.

datum co se přednášelo
15. 10. Toky v sítích: základní definice a věty, Fordův-Fulkersonův algoritmus, Dinicův algoritmus, symetrická formulace toku. Algoritmus Tří Indů.
22. 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. 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. Perfektní párování v regulárním bipartitním grafu pomocí redukce stupňů, souvislost s hranovým barvením.
29. 10. Pravděpodobnostní algoritmus na nejmenší řez v neorientovaném grafu (Karger-Stein).
5. 11. Ú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.
12. 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.
19. 11. Minimální kostry ještě jednou: 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. Obecný relaxační algoritmus a důkaz jeho korektnosti.
26. 11. Přednáška odpadá kvůli Dni otevřených dveří.
3. 12. Nejkratší cesty: Bellmanův-Fordův a Dijkstrův algoritmus coby speciální případy relaxace. 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.
10. 12. Potenciálová redukce a eliminace záporných hran. 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í. Sledy očima algebraikovýma.
17. 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.
7. 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.
14. 1. Pokračování rovinného kreslení (slidy): 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š